백준 1978번: 소수 찾기 (Python)

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

1978번: 소수 찾기

---

Level: Bronze II

Solved By: Sieve of Eratosthenes

 

파이썬으로 에라토스테네스의 체를 구현해보았습니다.

from sys import stdin

N = stdin.readline()

def getPrime(n):
    prime = []
    visited = [False for _ in range(0, n + 1)]
    visited[1] = True
    for i in range(2, n + 1):
        if visited[i] == True:
            continue
        for j in range(i+i, n + 1, i):
            visited[j] = True
    
    for i in range(2, n + 1):
        if not visited[i]:
            prime.append(i)
    return visited
    
prime_li = getPrime(1000)

li = [*map(int, stdin.readline().split())]

res = 0
for v in li:
    # print(v)
    if prime_li[v] == False:
        res += 1
        
print(res)