백준 알고리즘 1978번 소수 찾기(python)

소수 관련 문제는 아리토스테네스의 체 방식을 사용하면 효율적으로 풀 수 있다. 

종종 보게 될 알고리즘이니 기억해두면 좋을 것 같다.

n = int(input())
li = list(map(int, input().split()))
t_li = [1]*(max(li)+1)
for i in range(2, max(li)//2 + 1):
    if t_li[i] == 1:
        for j in range(i+i, max(li)+1, i):
            t_li[j] = 0
prime = []
for i in range(2, len(t_li)):
    if t_li[i] == 1:
        prime.append(i)
cnt = 0
for n in li:
    if n in prime:
        cnt += 1
print(cnt)