あくまで備忘録なんで雑に記録します試し割り法（高速化の為、２以上の、奇数だけ、√ｎまで）
①０・１は外す
②２は入れる
③先に偶数NG判定
④３以降√ｎまでの奇数で、割って判定
def is_prime(n):
if n == 0 or n == 1:#０・１は非素数
return False
elif n == 2:#２は素数
return True
elif n % 2 == 0:#先に２で割って偶数はアウト
return False
for i in range(3, int(n**0.5) + 1, 2):#３以上の奇数、√ｎまでで割る
if n % i == 0:
return False
return True
is_prime(9999973)#0.0002秒エラトステネスのふるい（リスト）
①０・１は外す
②２〜√ｎまで、Falseなら飛ばす（事前にさらに小さい素数の倍数はFalseにされているから）
③↑の理由で、初見は素数になるはずだから、スタートを『i × 2』にしておく
④最終的にTrueを出力
def primes_list(n):
is_prime = [True] * (n + 1)#まずはｎまでの数字、is_primeリスト全部Trueにする
is_prime[0] = False#０は非素数
is_prime[1] = False#１は非素数
for i in range(2, int(n**0.5) + 1):#２〜√ｎまでのiで回す
if not is_prime[i]:#Falseなら飛ばす（事前にさらに小さい素数の倍数はFalseにされているから）
continue
for j in range(i * 2, n + 1, i):#２〜初見はTrue（素数）だけど、その倍数は全てFalse
is_prime[j] = False#例：２なら[4,6,8...]、３なら[6,9,12...]、５なら[10.15...]をFalse
return [i for i in range(n + 1) if is_prime[i]]#is_primeリスト上のTrueにはそのままiを入れる
primes_list1(10**7)#約３秒若干改良したバージョン（偶数を省いて、奇数の奇数倍だけ調査）たいしてかわらない
def primes_list2(n):
is_prime = [True] * (n + 1)#まずはｎまでの数字、is_primeリスト全部Trueにする
is_prime[0] = False#０は非素数
is_prime[1] = False#１は非素数
for k in range(4, n+1, 2):#先に偶数だけ反転
is_prime[k] = False
for i in range(3, int(n**0.5) + 1, 2):#３〜√ｎの奇数(ステップ２)で回す
if not is_prime[i]:#Falseなら飛ばす（事前にさらに小さい素数の倍数はFalseにされているから）
continue
for j in range(i, n + 1, i * 2):#奇数の奇数倍は全てFalse
is_prime[j] = False#例：２なら[4,6,8...]、３なら[6,9,12...]、５なら[5,10,15...]をFalse
is_prime[i] = True#だけど初見だから、Trueに戻す
return [i for i in range(n + 1) if is_prime[i]]#is_primeリスト上のTrueにはそのままiを入れる
primes_list2(10**7)#約2.4秒エラトステネスのふるい（判定・おそい）
リストを作って判定は遅い
def is_prime(n):
primes_list = [True] * (n + 1)#まずはｎまでの数字、primes_listリスト全部Trueにする
primes_list[0] = False#０は非素数
if n != 0:
primes_list[1] = False#１は非素数
for i in range(2, int(n**0.5) + 1):#２〜√ｎまでのiで回す
if not primes_list[i]:#Falseなら飛ばす（事前にさらに小さい素数の倍数はFalseにされているから）
continue
for j in range(i * 2, n + 1, i):#２〜初見はTrue（素数）だけど、その倍数は全てFalse
primes_list[j] = False#例：２なら[4,6,8...]、３なら[6,9,12...]、５なら[10.15...]をFalse
return primes_list[n]#primes_list上の数値をそのまま返す
is_prime(9999973)#2.4秒
コメント