소수 찾기(에라토스테네스의 체)

날짜 : 2022. 10. 05

사용 언어 : python

 

문제

 

코드

import sys

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
a = [True] * (n + 1) # 소수 : True, 아니면 False
m = int(n ** 0.5)

for i in range(2, m + 1):
    if a[i] == True:
        for j in range(i*2, n + 1, i):
            a[j] = False

result = 0
for i in range(1, n):
    if a[i+1] == True:
        result += A[i]

print(result)

 

 

알게된 점

- 에라토스테네스의 체를 활용하는 것은 알고 있었으나 리스트 크기가 100,000까지 나왔기 때문에 시간초과가 한 번 나왔다.

- 그래서 에라토스테네스의 체를 좀 더 빠르게 구현할 방법을 찾아 보았고 위의 코드에서 m값을 통해 시간을 확 줄일 수 있다는 것을 알게 되었다.

- 상위 for문에서 m값을 넣어야 했는데 하위 for문에 넣는 바람에 첫 번째에 시간초과가 난 듯 하다.

 

 

참고 사이트

- https://velog.io/@junyp1/에라토스테네스의-체-파이썬-구현

에라토스테네스의 체 파이썬 구현