i(>=2)부터 i를 제외하고 나누어 떨어지는 수 소수 후보에서 제외
1000까지 소수 다 구하기
에라토스테네스의 소수 필요충분조건 : 2보다 크면서 자기 자신의 제곱근까지의 수에 나눠지지 않는 수
#include<iostream>
#include<vector>
using namespace std;
int a[1001];
int main() {
int n;
cin >> n;
vector<int> q;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
q.push_back(x);
}
int result = 0;
a[0] = 1;
a[1] = 1;
for (int i = 2; i < 1001; i++) {
for (int j = 2; j < 1001; j++) {
if (j % i == 0) {
if (j != i) {
a[j] = 1;
}
}
}
}
for (int i = 0; i < n; i++) {
if (a[q[i]]==0) {
result++;
}
}
cout<< result;
}