백준 1929번 소수 구하기 // C++

문제

 

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

입력

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

출력

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

 

---

 

풀이

 

에라토스테네스의 체를 활용하는 문제이다.

 

에라토스테네스의 체란, 2부터 시작해서 해당 소수의 모든 배수를 제외하고 제외되지 않은 다음 수로 넘어가서 같은 동작을 반복하다보면 소수만 남게 된다!

 

그렇게 소수만 남기면서 한 뒤, 원하는 범위 내의 소수를 출력하면 된다.

 

주의할 점은 1은 소수가 아니다!

---

 

코드

#include <iostream>

using namespace std;

int N, M;

bool num[1000001];

int nextSosu(int cur);

int main() {
	cin >> N >> M;

	int cur = 1;

	num[1] = true;

	while (true) {
		cur = nextSosu(cur);

		if (cur == -1)
			break;

		for (int i = 2;; i++) {
			if (i * cur > M)
				break;

			num[i * cur] = true;
		}
	}

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

int nextSosu(int cur) {
	for (int i = cur + 1; i <= M; i++) {
		if (!num[i])
			return i;
	}

	return -1;
}