[BOJ] 1978 - 소수 찾기

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	int n;
    cin >> n;
    vector<int> arr;
    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        arr.push_back(tmp);
    }
    sort(arr.begin(), arr.end());
    int max = arr[n - 1];
    bool* table = new bool[max + 1];
    table[0] = table[1] = true;
    for(int i = 2; i < max / 2 + 1; i++){
        if(!table[i]){
            for(int j = i * 2; j <= max; j+=i){
                table[j] = true;
            }
        }
    }
    int count = 0;
    for(int i = 0; i < n; i++){
        if(!table[arr[i]]) count++;
    }
    cout << count << endl;
}