Algorithm in A..Z - 에라토스테네스의 체

개념

소수를 판별하는 알고리즘

---

작동원리

1. 2부터 시작한다.

2. 방문하지 않은 숫자이면 그 숫자의 배수를 전부 체크한다.

3. 체크되지 않은 숫자는 소수이다.

---

시간복잠도

O(NloglogN)

---

문제

1978 소수찾기

www.acmicpc.net/problem/1978

1978번: 소수 찾기

---

코드

#include <iostream>
#include <vector>
using namespace std;

constexpr int MAX = 1000;

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

    int n;
    cin >> n;
    int answer = 0;
    while (n--) {
        int num;
        cin >> num;

        answer += isPrime[num];
    }

    cout << answer << "\n";
}