[baekjoon 1978] 소수 찾기- 소수, 에라토스테네스의 체 (C++)

www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

소수 판정 알고리즘인 에라토스테네스의 체를 이용해서 풀었다.

 

 - 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

(baekjoon 2960 에라토스테네스의 체 문제에서 참고)

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

따라서 소수 P를 찾은 뒤, 그것의 배수들을 모두 지워주면서 소수만 남아 있는 소수 배열을 만드는 것이다.

#include <iostream>

using namespace std;

bool check[1001];
int N, num, cnt;
int main() {
	cin >> N;
	check[1] = true;
	for (int i = 2; i < 1001; i++) {
		for (int j = i * 2; j < 1001; j += i) {
			if (!check[j])
				check[j] = true;
		}
	} // 소수 배열 완성
    
		for (int i = 0; i < N; i++) {
			cin >> num;
			if (!check[num])
				cnt++;
	}
	cout << cnt;
}

소수만 남겨두는 배열을 만드는 방향으로 풀었기 때문에, 소수의 배수를 지워주는 for문에서 첫 시작을 소수부터가 아닌 소수의 배수 중 다음 수부터 시작해야 한다.