greentea31's Note

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

풀이 과정

어떤 수 N이 소수임을 판정하려면 2부터 N-1까지 나누면서 나누어 떨어지는지 확인하면 된다.

=> 2부터 N/2까지만 나누어도 된다. N = a * b (2 <= a <= b <= N-1)에서 b는 N/2를 넘을 수 없다.

=> 2부터 rootN까지만 나누어도 된다. N = a * b (2 <= a <= b <= N-1) 에서 rootN 이하의 a를 발견하지 못했으면 b는 존재하지 않기 때문이다

이유: rootN 이상의 a가 존재하면 b = N / a인데 a가 rootN보다 크므로 b가 rootN보다 작게 된다. 근데 그러면 a <= b가 아니므로 존재할 수 없다.

따라서 2부터 rootN까지 나눠보면서 소수 판정을 진행하면 된다.

코드

import sys

N = int(sys.stdin.readline())
inPu = list(map(int, sys.stdin.readline().split()))
answer = 0
for i in inPu:
    if i == 1: continue
    primeFlag = True
    for K in range(2, int(i**(1/2)) + 1):
        if i % K == 0: primeFlag = False
    if primeFlag: answer += 1
    else: pass

print(answer)