[BOJ] 1978 / 소수 찾기 / Python 파이썬

[BOJ] 1978 / 소수 찾기 / Python 파이썬

[BOJ] 1978 / 소수 찾기 / Python 파이썬

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

1978번: 소수 찾기

 

풀이

주어진 N 개의 수 중, 소수의 개수를 구하는 문제이다.

 

주어지는 숫자가 1000 이하의 자연수 이므로, 1000 이하의 소수를 먼저 찾은 후 확인하는 방법으로 구하였다.

 

1000 이하의 소수는 에라토스테네스의 체 알고리즘을 사용하였다.

 

primes = [0, 0] + [1] * 1000

for i in range(2, 1001):
    if primes[i]:
        for j in range(i+i, 1001, i):
            primes[j] = 0

N = int(input())
nums = list(map(int, input().split()))
res = 0
for n in nums:
    if primes[n]:
        res += 1

print(res)