[백준 1978] 소수 찾기 (Python)

1978번: 소수 찾기

import sys

def is_prime(x) :
  import math
  if x < 2 : return False
  for i in range(2, int(math.sqrt(x))+1):
    if x%i == 0 :
      return False
  return True

n = int(sys.stdin.readline().strip())
arr = list(map(int, sys.stdin.readline().split()))

result = 0
for i in arr : 
  if is_prime(i) :
    result +=1
    
print(result)

 정수론에서는 꽤 유명한 에라토스테네스의 체를 Python으로 구현해둔 것이다. 1보다 큰 정수의 경우 자신의 제곱근보다 작은 수로 나누어지지 않는다면 소수라는 성질을 이용하여 문제를 해결할 수 있다.