快速确定一个数在 Python 中是否为质数 <1十亿 [英] Quickly determine if a number is prime in Python for numbers < 1 billion
问题描述
我目前在 python 中检查数字素性的算法是减慢 1000 万到 10 亿之间的数字.我希望它得到改进，因为我知道我永远不会得到超过 10 亿的数字.
My current algorithm to check the primality of numbers in python is way to slow for numbers between 10 million and 1 billion. I want it to be improved knowing that I will never get numbers bigger than 1 billion.
上下文是我无法获得足够快的实现来解决 Euler 项目的第 60 个问题:我在 75 秒内得到问题的答案，而我在 60 秒内需要它.http://projecteuler.net/index.php?section=problems&id=60
The context is that I can't get an implementation that is quick enough for solving problem 60 of project Euler: I'm getting the answer to the problem in 75 seconds where I need it in 60 seconds. http://projecteuler.net/index.php?section=problems&id=60
我可支配的内存很少，所以我无法存储 10 亿以下的所有质数.
I have very few memory at my disposal so I can't store all the prime numbers below 1 billion.
我目前正在使用调整为 6k±1 的标准试音师.还有比这更好的吗?对于这么大的数字，我是否已经需要使用 Rabin-Miller 方法.
I'm currently using the standard trial division tuned with 6k±1. Is there anything better than this? Do I already need to get the Rabin-Miller method for numbers that are this large.
primes_under_100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
def isprime(n):
if n <= 100:
return n in primes_under_100
if n % 2 == 0 or n % 3 == 0:
return False
for f in range(5, int(n ** .5), 6):
if n % f == 0 or n % (f + 2) == 0:
return False
return True
我该如何改进这个算法?
How can I improve this algorithm?
Precision:我是 Python 新手，只想使用 Python 3+.
Precision: I'm new to python and would like to work with python 3+ only.
最终代码
有兴趣的朋友，利用MAK的思路，我生成了以下代码，速度快了1/3左右，让我在不到60秒的时间内得到欧拉问题的结果！
For those who are interested, using MAK's ideas, I generated the following code which is about 1/3 quicker, allowing me to get the result of the euler problem in less than 60 seconds!
from bisect import bisect_left
# sqrt(1000000000) = 31622
__primes = sieve(31622)
def is_prime(n):
# if prime is already in the list, just pick it
if n <= 31622:
i = bisect_left(__primes, n)
return i != len(__primes) and __primes[i] == n
# Divide by each known prime
limit = int(n ** .5)
for p in __primes:
if p > limit: return True
if n % p == 0: return False
# fall back on trial division if n > 1 billion
for f in range(31627, limit, 6): # 31627 is the next prime
if n % f == 0 or n % (f + 4) == 0:
return False
return True
推荐答案
对于大到 10^9 的数字，一种方法可以是生成直到 sqrt(10^9) 的所有素数，然后简单地检查根据该列表中的数字输入数字.如果一个数不能被任何其他小于或等于其平方根的素数整除，则它本身必须是素数(它必须至少有一个因子 <=sqrt 并且另一个 >= sqrt 不是素数).请注意，您不需要测试所有数字的可整性，只需测试平方根(大约 32,000 - 我认为很容易控制).您可以使用 sieve 生成素数列表.
For numbers as large as 10^9, one approach can be to generate all primes up to sqrt(10^9) and then simply check the divisibility of the input number against the numbers in that list. If a number isn't divisible by any other prime less than or equal to its square root, it must itself be a prime (it must have at least one factor <=sqrt and another >= sqrt to not be prime). Notice how you do not need to test divisibility for all numbers, just up to the square root (which is around 32,000 - quite manageable I think). You can generate the list of primes using a sieve.
您也可以进行概率素数测试.但是它们可能更难理解，对于这个问题，只需使用生成的素数列表就足够了.
You could also go for a probabilistic prime test. But they can be harder to understand, and for this problem simply using a generated list of primes should suffice.
这篇关于快速确定一个数在 Python 中是否为质数 <1十亿的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
