[파이썬] 소수 판별 '에라토스테네스의 체'

728x90

에라토스테네스의 체

 

1. 소수를 구하고자 하는 범위를 2부터 나열

 

2~n 사이의 소수를 구하고자 할 때 다음과 같이 나열합니다.

0과 1은 False로 두고, 2~n-1개까지 True로 둡니다. 

a = [False,False] + [True]*(n-1)

 

2. 2부터 나열한 수까지 반복하며 배수 지우기

 

• 2부터 n+1까지 반복문을 돌리고 a의 i 번째 인덱스가 True 이면 primes 리스트에 추가합니다.
• 만약 n=10, i= 2이면, 현재 a[2]는 True이므로 primes에 2를 추가하고 2의 배수인 4,8이 False가 됩니다.
• 3도 primes에 추가되고 배수인 6,9가 False가 됩니다.
• 4는 2의 배수를 지우는 단계에서 False가 되었으므로 if문을 통과하지 못합니다.
• 5는 True 이므로 primes에 추가되고 배수인 10이 False가 됩니다.
• 10까지 위 과정을 반복합니다.

n=10
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)

결국 primes = [2,3,5,7] 이 됩니다.

 

[파이썬/코딩테스트] - [프로그래머스/파이썬] 소수 찾기

[프로그래머스/파이썬] 소수 찾기