[C++] 백준 BOJ 1978 소수 찾기

문제 링크 : https://boj.kr/1978

이 문제는 에라토스테네스의 체를 이용하여 소수 리스트를 미리 구한다음 계산하면 쉽게 답을 찾을 수 있다.

입력 최대값이 1000밖에 안되기 때문에 그냥 1000까지 미리 소수를 구하는 편이 빠른 것 같다.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    bool isPrime[1001];
    memset(isPrime, true, sizeof(isPrime));
 
    // 에라토스테네스의 체 이용하여 1000까지의 소수 구하기
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 2; i <= 1000; i++) {
        if (isPrime[i]) {
            // 소수의 N배수들은 모두 소수가 아님
            for (int j = 2 * i; j <= 1000; j += i)
                isPrime[j] = false;
        }
    }
    int num, input, result = 0;
    cin >> num;
    while(num--){
        cin >> input;
        if(isPrime[input])
            result++;
    }
    cout << result;
 
    return 0;
}