1978_소수 찾기

bgy·2022년 1월 5일
0

백준

목록 보기
12/21

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;  
}

0개의 댓글