[アルゴリズム]アラトスとか


典型的な素数判別アルゴリズムは,大量の素数を迅速かつ正確に求めることができる.
最大1000個の小数、N番目の小数など
簡単に言えば、NへのTrue配列を作成し、brootポートに移動し、i*2の配列がすべてFalseになるようにします.
iが2の場合の様子

探索しながら、倍数をFalseにします.

簡単なPythonコード
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)