快速确定Python中的数字是否为数字<10亿

Question

我目前用于检查python中数字素数的算法可以减慢1000万到10亿之间的数字.我希望它得到改善,因为我知道我永远不会得到超过10亿的数字.

上下文是我无法获得足够快的解决方案来解决项目Euler的问题60:我在75秒内得到问题的答案,我需要在60秒内完成.http://projecteuler.net/index.php?section=problems&id=60

我的内存很少,所以我无法存储10亿以下的所有素数.

我目前正在使用以6k±1调谐的标准试验部门.还有什么比这更好的吗？我是否已经需要使用Rabin-Miller方法来获得如此大的数字.

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

如何改进此算法？

精度:我是python的新手,只想使用python 3+.

---

最终代码

对于那些感兴趣的人,使用MAK的想法,我生成了以下代码,大约快1/3,让我在不到60秒的时间内得到欧拉问题的结果!

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

Answer 1

对于大到10 ^ 9的数字,一种方法可以生成直到sqrt(10 ^ 9)的所有素数,然后简单地检查输入数与该列表中的数字的可分性.如果一个数字不能被小于或等于其平方根的任何其他素数整除,则它本身必须是一个素数(它必须至少有一个因子<= sqrt而另一个> = sqrt才能成为素数).请注意你不需要测试所有数字的可分性,只需要达到平方根(大约32,000 - 我认为非常易于管理).您可以使用筛子生成素数列表.

你也可以去进行概率素数测试.但是它们可能更难理解,对于这个问题,仅仅使用生成的素数列表就足够了.

Answer 2

为了解决Project Euler问题,我在你的问题中做了你的建议:实现Miller Rabin测试(在C#中,但我怀疑它在Python中也会很快).算法并不困难.对于低于4,759,123,141的数字,足以检查一个数字是基数2,7,61的强伪素数.将其与小数的试验除法相结合.

我不知道你到目前为止解决了多少问题,但是你可以使用快速素数测试对很多问题都有很大的价值.