문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1≤M≤N≤1,000,000)

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력/출력

코드

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX_SIZE 1000000
using namespace std;

int main() {
	int M, N, min = 10001, sum = 0;
	bool not_prime_num[MAX_SIZE + 5] = {false, };

	not_prime_num[1] = true;

	for (int item = 2; item <= MAX_SIZE;item++) {
		if (not_prime_num[item] == false) {
			for (int i = 2; i*item <= MAX_SIZE; i++) 
					not_prime_num[i*item] = true; // 소수가 아닌 수 지움
		}
	}

	scanf("%d %d", &M, &N);

	for (int i = M; i <= N; i++)
		if (!not_prime_num[i])
			printf("%d\n", i);

	return 0;
}

풀이

소수 찾기 알고리즘으로 유명한 에라토스테네스의 체 방법을 이용해 구현해보았다.
소수의 배수에 해당하는 숫자들을 모두 지워나가는 방식이다.
시간복잡도는 O(nlog(logn))으로 짧다.