在间隔中找到素数的最快方法

Question

我尝试搜索 StackOverflow 和其他一些资源以找到在某个时间间隔内获取素数的最快方法，但我没有找到任何有效的方法，所以这是我的代码：

def prime(lower,upper):

   prime_num = []

   for num in range(lower, upper + 1):

       # all prime numbers are greater than 1

       if num > 1:

           for i in range(2, num):

               if (num % i) == 0:

                   break

           else:

               prime_num.append(num)

   return prime_num

我可以提高效率吗？

我尝试以Fastest way to find prime number找到我的答案，但我没有在区间内找到素数。

Answer 1

我使用 MillerRabin 编写了一个基于方程式的素数查找器，它不如筛选的 next_prime 查找器快，但它可以创建大素数，并且您可以得到它用来执行此操作的方程式。这是一个例子。接下来是代码：In [5]: random_powers_of_2_prime_finder(1700)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Out[5]: 'pow_mod_p2(27667926810353357467837030512965232809390030031226210665153053230366733641224969190749433786036367429621811172950201894317760707656743515868441833458231399831181835090133016121983538940390210139495308488162621251038899539040754356082290519897317296011451440743372490592978807226034368488897495284627000283052473128881567140583900869955672587100845212926471955871127908735971483320243645947895142869961737653915035227117609878654364103786076604155505752302208115738401922695154233285466309546195881192879100630465, 2**1700-1, 2**1700) = 39813813626508820802866840332930483915032503127272745949035409006826553224524022617054655998698265075307606470641844262425466307284799062400415723706121978318083341480570093257346685775812379517688088750320304825524129104843315625728552273405257012724890746036676690819264523213918417013254746343166475026521678315406258681897811019418959153156539529686266438553210337341886173951710073382062000738529177807356144889399957163774682298839265163964939160419147731528735814055956971057054406988006642001090729179713'or use to get the answer directly:In [6]: random_powers_of_2_prime_finder(1700, withstats=False)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;Out[6]: 4294700745548823167814331026002277003506280507463037204789057278997393231742311262730598677178338843033513290622514923311878829768955491790776416394211091580729947152858233850115018443160652214481910152534141980349815095067950295723412327595876094583434338271661005996561619688026571936782640346943257209115949079332605276629723961466102207851395372367417030036395877110498443231648303290010952093560918409759519145163112934517372716658602133001390012193450373443470282242835941058763834226551786349290424923951代码：import randomimport mathdef primes_sieve2(limit):&nbsp; &nbsp; a = [True] * limit&nbsp; &nbsp; a[0] = a[1] = False&nbsp; &nbsp; for (i, isprime) in enumerate(a):&nbsp; &nbsp; &nbsp; &nbsp; if isprime:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield i&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for n in range(i*i, limit, i):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a[n] = Falsedef ltrailing(N):&nbsp; &nbsp; return len(str(bin(N))) - len(str(bin(N)).rstrip('0'))def pow_mod_p2(x, y, z):&nbsp; &nbsp; "4-5 times faster than pow for powers of 2"&nbsp; &nbsp; number = 1&nbsp; &nbsp; while y:&nbsp; &nbsp; &nbsp; &nbsp; if y & 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; number = modular_powerxz(number * x, z)&nbsp; &nbsp; &nbsp; &nbsp; y >>= 1&nbsp; &nbsp; &nbsp; &nbsp; x = modular_powerxz(x * x, z)&nbsp; &nbsp; return numberdef modular_powerxz(num, z, bitlength=1, offset=0):&nbsp; &nbsp;xpowers = 1<<(z.bit_length()-bitlength)&nbsp; &nbsp;if ((num+1) & (xpowers-1)) == 0:&nbsp; &nbsp; &nbsp; return ( num & ( xpowers -bitlength)) + 2&nbsp; &nbsp;elif offset == -1:&nbsp; &nbsp; &nbsp; return ( num & ( xpowers -bitlength)) + 1&nbsp; &nbsp;elif offset == 0:&nbsp; &nbsp; &nbsp; return ( num & ( xpowers -bitlength))&nbsp; &nbsp;elif offset == 1:&nbsp; &nbsp; &nbsp; return ( num & ( xpowers -bitlength)) - 1&nbsp; &nbsp;elif offset == 2:&nbsp; &nbsp; &nbsp; return ( num & ( xpowers -bitlength)) - 2def MillerRabin(N, primetest, iterx, powx, withstats=False):&nbsp;&nbsp; primetest = pow(primetest, powx, N)&nbsp;&nbsp; if withstats == True:&nbsp; &nbsp; &nbsp;print("first: ",primetest)&nbsp;&nbsp; if primetest == 1 or primetest == N - 1:&nbsp;&nbsp; &nbsp; return True&nbsp;&nbsp; else:&nbsp;&nbsp; &nbsp; for x in range(0, iterx-1):&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;primetest = pow(primetest, 2, N)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;if withstats == True:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; print("else: ", primetest)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;if primetest == N - 1: return True&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;if primetest == 1: return False&nbsp;&nbsp; return False&nbsp;PRIMES=list(primes_sieve2(1000000))def mr_isprime(N, withstats=False):&nbsp; &nbsp; if N == 2:&nbsp; &nbsp; &nbsp; return True&nbsp; &nbsp; if N % 2 == 0:&nbsp; &nbsp; &nbsp; return False&nbsp; &nbsp; if N < 2:&nbsp; &nbsp; &nbsp; &nbsp; return False&nbsp; &nbsp; if N in PRIMES:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return True&nbsp; &nbsp; for xx in PRIMES:&nbsp; &nbsp; &nbsp; &nbsp;if N % xx == 0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return False&nbsp; &nbsp; iterx = ltrailing(N - 1)&nbsp; &nbsp; k = pow_mod_p2(N, (1<<N.bit_length())-1, 1<<N.bit_length()) - 1&nbsp; &nbsp; t = N >> iterx&nbsp; &nbsp; tests = [k+1, k+2, k, k-2, k-1]&nbsp; &nbsp; for primetest in tests:&nbsp; &nbsp; &nbsp; &nbsp; if primetest >= N:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; primetest %= N&nbsp; &nbsp; &nbsp; &nbsp; if primetest >= 2:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if MillerRabin(N, primetest, iterx, t, withstats) == False:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return False&nbsp; &nbsp; return Truedef lars_last_modulus_powers_of_two(hm):&nbsp; &nbsp;return math.gcd(hm, 1<<hm.bit_length())def random_powers_of_2_prime_finder(powersnumber, primeanswer=False, withstats=True):&nbsp; &nbsp; while True:&nbsp; &nbsp; &nbsp; &nbsp;randnum = random.randrange((1<<(powersnumber-1))-1, (1<<powersnumber)-1,2)&nbsp; &nbsp; &nbsp; &nbsp;while lars_last_modulus_powers_of_two(randnum) == 2 and&nbsp; mr_isprime(randnum//2) == False:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;randnum = random.randrange((1<<(powersnumber-1))-1, (1<<powersnumber)-1,2)&nbsp; &nbsp; &nbsp; &nbsp;answer = randnum//2&nbsp; &nbsp; &nbsp; &nbsp;# This option makes the finding of a prime much longer, i would suggest not using it as&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;# the whole point is a prime answer.&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;if primeanswer == True:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if mr_isprime(answer) == False:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue&nbsp; &nbsp; &nbsp; &nbsp;powers2find = pow_mod_p2(answer, (1<<powersnumber)-1, 1<<powersnumber)&nbsp; &nbsp; &nbsp; &nbsp;if mr_isprime(powers2find) == True:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; &nbsp; &nbsp;else:&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue&nbsp; &nbsp; if withstats == False:&nbsp; &nbsp; &nbsp; return powers2find&nbsp; &nbsp; elif withstats == True:&nbsp; &nbsp; &nbsp; return f"pow_mod_p2({answer}, 2**{powersnumber}-1, 2**{powersnumber}) = {powers2find}"&nbsp; &nbsp; return powers2finddef nextprime(N):&nbsp; &nbsp;N+=2&nbsp; &nbsp;while not mr_isprime(N):&nbsp; &nbsp; &nbsp; N+=2&nbsp; &nbsp;return Ndef get_primes(lower, upper):&nbsp; &nbsp; lower = lower|1&nbsp; &nbsp; upper = upper|1&nbsp; &nbsp; vv = []&nbsp; &nbsp; if mr_isprime(lower):&nbsp; &nbsp; &nbsp; vv.append(lower)&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; vv=[nextprime(lower)]&nbsp; &nbsp; while vv[-1] < upper:&nbsp; &nbsp; &nbsp; &nbsp;vv.append(nextprime(vv[-1]))&nbsp; &nbsp; return vv这是一个像你这样的例子：In [1538]: cc = get_primes(1009732533765201, 1009732533767201)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;In [1539]: print(cc)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;[1009732533765251, 1009732533765281, 1009732533765289, 1009732533765301, 1009732533765341, 1009732533765379, 1009732533765481, 1009732533765493, 1009732533765509, 1009732533765521, 1009732533765539, 1009732533765547, 1009732533765559, 1009732533765589, 1009732533765623, 1009732533765749, 1009732533765751, 1009732533765757, 1009732533765773, 1009732533765821, 1009732533765859, 1009732533765889, 1009732533765899, 1009732533765929, 1009732533765947, 1009732533766063, 1009732533766069, 1009732533766079, 1009732533766093, 1009732533766109, 1009732533766189, 1009732533766211, 1009732533766249, 1009732533766283, 1009732533766337, 1009732533766343, 1009732533766421, 1009732533766427, 1009732533766457, 1009732533766531, 1009732533766631, 1009732533766643, 1009732533766667, 1009732533766703, 1009732533766727, 1009732533766751, 1009732533766763, 1009732533766807, 1009732533766811, 1009732533766829, 1009732533766843, 1009732533766877, 1009732533766909, 1009732533766933, 1009732533766937, 1009732533766973, 1009732533767029, 1009732533767039, 1009732533767093, 1009732533767101, 1009732533767147, 1009732533767159, 1009732533767161, 1009732533767183, 1009732533767197, 1009732533767233]

Answer 2

是的，您可以提高效率。如前所述，对于非常大的数字，请使用 Miller-Rabin。对于较小的范围，请使用埃拉托色尼筛法。但是，除此之外，您的主要检查代码效率非常低。2 是唯一的偶质数，它可以让你做一半的工作。您只需要检查您正在测试的数字的平方根。在任何一对因数中：f 和 n/f，一个保证小于或等于被测数的平方根。一旦你找到一个因素，那么这个数字就是复合的。我的 Python 不好，所以这是伪代码：isPrime(num)&nbsp; // Negatives, 0, 1 are not prime.&nbsp; if (num < 2) return false&nbsp; // Even numbers: 2 is the only even prime.&nbsp; if (num % 2 == 0) return (num == 2)&nbsp;&nbsp;&nbsp; // Odd numbers have only odd factors.&nbsp; limit <- 1 + sqrt(num)&nbsp; for (i <- 3 to limit step 2)&nbsp; &nbsp; if (num % i == 0) return false&nbsp;&nbsp;&nbsp; // No factors found so num is prime&nbsp; return true&nbsp;&nbsp;end isPrime

Answer 3

是的。一般来说，使用：埃拉托色尼筛法米勒-拉宾素数检验其他选项包括尝试编译语言，如 C++，但我认为这不是您要找的，因为您已经询问过 Python。