[C++] 백준 1929번 소수 구하기 (에라토스테네스의 채)

 m과 n을 입력받고 m과 n 사이에 있는 소수를 출력하는 프로그램이다. 단, 에라토스테네스의 채를 이용해서 풀어야한다.

 미리 1~1000000 까지의 수 중에서 소수인 수를 걸러내고, m부터 n까지의 값 중 소수인 것을 출력한다.

 

#include <stdio.h>


int main() {

	bool num[1000001];
    
	int m, n;
        int i, j;
	
	scanf("%d %d", &m, &n);

	for (i = 2; i <= 1000000; i++) {
		num[i] = true;
	}

	num[1] = false;

	for (i = 2; (i*i) <= 1000000; i++) {

		if (num[i] == true) {

			for (j = i + i; j <= 1000000; j += i) {

				num[j] = false;

			}

		}

	}

	for (i = m; i <= n; i++) {
		if (num[i])
			printf("%d\n", i);
	}

	return 0;

}