[백준 C++] 1929번: 소수 구하기

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

#include <iostream>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, M;
	cin >> N >> M;
 
	for (int i = N;i <= M;i++) {
		bool b = true;
		for (int j = 2;j < i;j++) {
			if (i % j == 0) {
				b = false;
				break;
			}
		}
		if (b && i != 1)
			cout << i << "\n";
	}
 
	return 0;
}

 

처음 썼던 코드 이중 포문을 사용하여 O(n 루트 n)인데 n의 값이 1000000이여서 시간초과가 발생하였다. 

 

혹시 몰라

ios_base::sync_with_stdio(false);
	cin.tie(NULL);

 

문장도 삽입해서 다시 실행해 보았지만 역시나 시간 초과

 

이중 포문을 사용하지 않고 소수를 구하는 방법을 찾자.

 

bool 배열을 백만개를 만들어서 미리 어떤게 소수인지 구한다음 출력하는 방식 

 

소수를 구하는게 아니라 2부터 곱해지는 배수가 있는 수를 미리 다 지워논다. ex) 2, 4, 6... 은 소수가 아니기 때문

 

(하지만 우리가 알고 싶은 범위는 N 까지 이므로 i *  i = N 까지 구한다 )

 

 

이렇게 푸는 방법을 에라토스테네스의 체라고도 부른다.

 

이 방법의 시간복잡도는 O(N log(log N) 이 된다. 

 

N과 M의 위치도 달라져 있기 때문에 바꿔주었다.

#include <iostream>
using namespace std;
bool arr[1000001] = { false, };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int M, N;
	cin >> M >> N;
	arr[0] , arr[1] = true;
	for (int i = 2;i * i<= N;i++) {
		if (arr[i])
			continue;
		else {
			for (int j = 2; j * i <= N;++j) {
				arr[i * j] = true;
			}
		}
	}
	
	for (int i = M; i <= N; i++) {
		if (!arr[i])
			cout << i << "\n";
	}
 
	return 0;
}

 

제출내역보니까 이전에도 풀었던 문제인데 방법을 떠올리기가 막상 쉽지 않은거 같다.