前回の記事の最後に書いた、決定的な素数判定と確率的な素数判定をハイブリッドにしたら最強なんじゃないかという考えのもと、最強の素数判定器を作ってみた。
特にひねりはないが、最初に3桁まで(引数で指定可能)の素数リストを作っておいて、確率的な素数判定にかける前に合成数を弾くというやり方。
swdrsker.hatenablog.com
純粋なエラトステネスの篩やミラーラビン素数判定法と比べて、
精度的には、並のカーマイケル数では太刀打ちできないはずなので精度も向上。
時間的にも、ちょっとした合成数なら最初から弾かれるので一瞬。
数百桁で本当に素数のものが現れたらちょっと時間がかかるかもしれないってくらい。
import random
import numpy as np
class PrimeChecker:
def __init__(self, list_limit = pow(10,3)):
if list_limit < 5: list_limit = 5
self.prime_list = self.set_prime_list(list_limit)
self.list_limit = list_limit
@staticmethod
def set_prime_list(n):
def mark(primes,x):
for i in xrange(2*x, n+1, x):
primes[i-2] = False
primes = [(i%2!=0 and i%3!=0 and i%5!=0) for i in range(2,n+1)]
primes[0] = primes[1] = primes[3] = True
for x in xrange(7, int(np.sqrt(n+1))+1):
if primes[x-2]: mark(primes, x)
prime_list = []
for i in range(n-1):
if primes[i]: prime_list.append(i+2)
return prime_list
def is_prime(self, n):
k = 50
if n < self.list_limit: return True if n in self.prime_list else False
for prime in self.prime_list:
if n%prime == 0: return False
else:
s, d = 0, n-1
while d%2==0: s,d = s+1, d/2
while k > 0:
k = k-1
a = random.randint(1,n-1)
t, y = d, pow(a,d,n)
while t != n-1 and y != 1 and y != n-1:
y = pow(y,2,n)
t <<= 1
if y != n-1 and t%2 == 0:
return False
return True
if __name__=="__main__":
pc = PrimeChecker()
pc.is_prime(58427)
PrimeCheckerのインスタンス化の引数で素数リストの数の上限を決めるんだけど、
素数リストがデカすぎると
最初にインスタンス化する時に時間がかかるのと、リスト内の走査に時間がかかるので
実行時間的には、初期化する素数リストは3,4桁が使いやすそう。