백준 1978 파이썬 python : 소수 찾기 @@황소처럼 우직하게@@ 에라토네스의 체

import sys
input = sys.stdin.readline

n = int(input())
num_list = list(map(int, input().split()))

num_max = max(num_list)

mat = [1 for i in range(num_max + 1)]
mat[1] = 0

i = 2
while i <= num_max:
    if mat[i] == 1:
        for j in range(i + i, num_max + 1, i):
            mat[j] = 0
    i += 1

ans = 0
for x in num_list:
    if mat[x] == 1:
        ans += 1
print(ans)