[백준] 1929번 소수 구하기

1929번: 소수 구하기

처음엔 원래 소수 구하던 방식으로 짰는데 자꾸 시간 초과가 되길래

효율적으로 소수 짜는 법을 검색해보니 에라토스테네스의 체 알고리즘이 나왔다.

 

 

2부터 원하는 범위까지의 수를 배열에 넣고

소수가 아닌 수들을 체크하는 방식이다.

​

2의 배수들을 체크

3의 배수들을 체크

4는 2의 배수로 체크가 되어 있어 넘어간다

5의 배수들을 체크

...

​

이런 식으로 나아가며 체크되지 않은 수들이 소수이다.

물론 무작정 이중 for문으로 가차 없이 돌려버리면 최악의 시간이 나온다.

​

안쪽 for문의 증감식을 변형시켜 i의 배수만 체크할 수 있도록 만들고

이미 체크되어 있는 수들은 continue로 먹금 시켜주면 최선의 알고리즘을 만들 수 있다.

#include <iostream>
using namespace std;
int arr[1000001] = { 0 };

int main() {
	int M, N;
	cin >> M >> N;
	arr[1] = -1;
	for (int i = 2; i <= N; i++) {
		if (arr[i] == -1)continue;
		for (int j = i; j <= N; j += i) {
			if (j != i && j % i == 0)arr[j] = -1;
		}
	}
	for (int i = M; i <= N; i++) {
		if (arr[i] == 0)cout << i << "\n";
	}
	return 0;
}
​