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

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

 

풀이

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    // 아리토스테네스의 체
    vector<bool> isPrime(1001, true);
    isPrime[1] = false;
    for(int i=2; i<1001; i++) {
        if(!isPrime[i])
            continue;
        for(int j=i*i; j<1001; j+=i)
            isPrime[j] = false;
    }
    
    // 입력
    int n;
    cin >> n;
    vector<int> input(n);
    for(int i=0; i<n; i++)
        cin >> input[i];
    
    // 연산
    int ans = 0;
    for(int i=0; i<n; i++) {
        if(isPrime[input[i]])
            ans++;
    }
    
    // 출력
    cout << ans;
    
    return 0;
}