BOJ 1978번 소수 찾기

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/1978/1978/%EC%86%8C%EC%8A%A4.cpp

 

소수를 찾기위한 정확한 개념을 기억해두자.

** 소수는 소수로 나누어떨어지지 않는다.

 

//에라토스테네스의 체
#include <iostream>
using namespace std;
 
#define MAX 1001
 
bool sosu[MAX];
 
int main() {
    for (int i = 2; i < MAX; i++) sosu[i] = true;
 
    for (int i = 2; i * i < MAX; i++) {
        if (!sosu[i]) continue;
        for (int k = i * i; k < MAX; k += i) sosu[k] = false;
    }
 
    int N,n, cnt=0; cin >> N;
 
    while (N--) {
        cin >> n;
        cnt += sosu[n];
    }
 
    cout << cnt;
    return 0;
}