1978번: 소수 찾기

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N(N≤100)이 주어진다.
다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

알고리즘 분류

• 수학, 정수론, 소수 판정, 에라토스테네스의 체

나의 풀이

import sys
input = input.stdin.readline
n = int(input().rstrip())
nums = list(map(int, input().split()))

prime = []
prime_init = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

for i in range(2, 1001) :
    P = True
    for k in prime_init :
        if i%k ==0 : P = False
    if P : prime.append(i)
prime = prime_init + prime

cnt = 0

for i in nums :
    if i in prime :
        cnt += 1
print(cnt)

에라토스테네스의 체를 사용하여 N (2≤N≤1000)이 prime_init (list : 31이하의 소수)의 원소들로 나누어 떨어지지 않는다면 prime 리스트에 append 한다.

$31^{10} < 1000 < 32^{2}$

What I learned

에라토스테네스의 체(위키피디아)