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

문제

1978번: 소수 찾기 (acmicpc.net)

1978번: 소수 찾기

코드

#include <iostream>
#include <vector>

#define SIZE 1000

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<bool> isPrime(SIZE + 1, true);
    isPrime[1] = false;
    for (int i = 2; i * i <= SIZE; i++) {
        if (!isPrime[i]) continue;
        for (int j = i * i; j <= SIZE; j += i) {
            isPrime[j] = false;
        }
    }

    int cnt = 0;
    int n;
    cin >> n;
    while (n--) {
        int num;
        cin >> num;
        if (isPrime[num]) cnt++;
    }
    cout << cnt;
    return 0;
}

 

설명

에라토스테네스의 체 알고리즘을 이용하여 1000 이하의 소수를 판별한다.