[수학] 에라토스테네스의 체(with python)

백준 1978번 솔루션을 구글링해보니 '에라토스테네스의 체'를 이용한 풀이가 종종 보였다.

 

 

참고 링크 :https://gururuglasses.tistory.com/80

[ Algorithm ] 에라토스테네스의 체 ( Python )( 소수를 구하는 방법)

 

에라토스테네스의 체?

 

O(NloglogN)의 시간복잡도를 이용해 소수를 찾는 방법으로 2부터 N까지의 모든 소수를 찾는 방법이다.

 

다수의 소수를 찾을 때 유용하나 메모리가 많이 필요하다는 단점이 있다.

 

따라서 n이 1,000,000 이내일 때 사용하는 것이 좋다.

 

n = int(input())

sieve = [True] * (n+1) #주어진 모든 수 나열

m = int(n ** 0.5) #n의 제곱근을 구해줌 -> 가운데 수를 기준으로 대칭적이기 때문

for i in range(2, m+1): #자기 자신은 남겨두어야 하기 때문에 2부터 시작
  if sieve[i] == True:
    for j in range(2*i, n+1, i):
      sieve[j] = False

print([i for i in range(2,n+1) if sieve[i] == True]) #True 자리에 숫자 i 대입 후 print

 

관련 문제

1978 소수 찾기 O (실버5)

1929 소수 구하기 O (실버3)

2960 에라토스테네스의 체 O (실버4)

4948 베르트랑 공준

9020 골드바흐의 추측

1644 소수의 연속합