[1929번] 소수 구하기

1929번: 소수 구하기

 

www.acmicpc.net

M이상 N이하의 소수를 모두 출력하는 문제이다.

범위가 1 <= M <= N <= 1,000,000 이기 때문에 1978번과 같이 

자기 자신보다 작은 수를 나눠서 소수를 판별하기에는 많은 시간이 걸린다.

실제로 제출해 보면 시간초과가 난다.

해결법은  1. 최적화 2. 다른 방식의 접근 이 있는데 다른 방식의 접근으로 풀어보았다.

에라토스테네스의 체를 이용하여 n까지의 소수를 구할 때, 잘 보면 n까지 모든 수의 배수를 다 나눠 볼 필요가 없다는 점이 보인다.

만약 어떤수 m = ab 라면 a 와 b 중 적어도 하나는 √n 이라는 사실을 알 수 있다. 즉, n보다 작은 합성수 m은 √n보다 작은 수의 배수만  체크해도 전부 지워진다.

/*1929번 소수 구하기*/
#include <iostream>
using namespace std;
int M, N;
int num[1000001] = {0,-1,};//0 : 소수, -1 : 1 또는 합성수

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> M >> N;

	for (int i = 2; i*i <= N; i++) { //체크 범위를 √N 까지로 둔다.
		for (int j = i * i; j <= N; j += i) {//i의 배수 부분을 다 합성수로 체크한다.
			if (num[j] == -1) continue;//만약 이전에 처리가 되었다면 바로 다음으로 넘어간다.
			num[j] = -1;
		}
	}
	for (int i = M; i <= N; i++) {
		if (num[i] == 0) cout << i << '\n';
	}
}