1978번 소수 찾기

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

에라토스테네스의 체이다.

살짝 잊었나 보다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
bool prime[1001] = { true, };
 
void pn()
{
    int sq = sqrt(1000);
    
    for (int i = 2; i <= sq; i++)
    {
        for (int j = 2 * i; j <= 1000; j += i)
        {
            if (!prime[i]) continue;
 
            prime[j] = false;
        }
    }
}
 
int main(void)
{
    int n = 0, ans = 0, number = 0;
 
    memset(prime, true, sizeof(prime));
 
    pn();
 
    prime[1] = false;
 
    scanf("%d", &n);
 
    while (n--)
    {
        scanf("%d", &number);
 
        if (prime[number]) ++ans;
    }
 
    printf("%d\n", ans);
 
    return 0;
}