[알고리즘] 에라토스어쩌구저쩌구의 체

대표적인 소수판별 알고리즘으로 다량의 소수를 빠르고 정확하게 구할 수 있다.

Ex) 1000까지 소수가 몇개 있는지, N번째 소수는 무엇인지 등

간단하게 말하면 N까지의 True 배열을 만들고, 브루트포트 탐색하여 i*2인 배열을 모두 False로 만든다.

i가 2일때의 모습

탐색하면서 배수를 다 False로 만든다.

간단한 파이썬 코드

n=1000
#0,1번째 인덱스는 False 소수가 아님
a=[False,False] + True * (n+1)
prime = list()

for i in range(2,n+1):
	if a[i]:
	    prime.appned(i)
            #i를 1씩더함, 2*1, 2*2, 2*3, 2*4.... 인덱스를 참조 
            for j in range(2*i,n+1,i):
            	a[j] = False

#소수인 모든 리스트를 출력
print(prime)