1978번: 소수 찾기

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


$O(n\sqrt a)$

1이 아닌 어떤 수 x가 2~rt(x)로 나누어 떨어지지 않는다면 소수이다.

#include<cstdio>
int n, r;
int main() {
    scanf("%d", &n);
    r = n;
    for (int i = 0, x; i < n; i++) {
        scanf("%d", &x);
        if (x == 1) r--;
        for (int j = 2; j*j <= x; j++)
            if (x%j == 0) { r--; break; }
    }
    printf("%d", r);
    return 0;
}