使用编译提高程序效率

Question

我已经为生成素数制作了一个筛子。我正在进行一个关于RSA的学校项目，其中包括一些编程。我将使用这些素数来构建RSA系统，但因为这是我的论文，安全性并不是非常重要。然而，大素数更具挑战性，我很喜欢这个。 我使用的代码:

def Zeef(a):
    import math
    upperBound = a
    upperBoundSquareRoot = int(math.sqrt(upperBound))
    isPrime = [1 for m in range (0,upperBound+1)]
    for m in range(2,upperBoundSquareRoot+1):
        if (isPrime[m]==1):
            for k in range(m*m,upperBound+1,m):
                isPrime[k] = 0;
    print("Priemgetallen : ")
    numberofPrimes = 0
    for m in range(2,upperBound+1):
        if (isPrime[m] ==1):
            print(m)
            numberofPrimes = numberofPrimes+1
    print("Aantal = " , numberofPrimes);
a=input("Alle priemgetallen tot: ")
aa=int(a)
Priemen = Zeef(aa)

我相信有更快的方法来生成质数，但是我现在对改进代码不太感兴趣。当我运行这个函数时，它可以很好地生成七位质数，但是当我想要更多时，它就变得非常慢。我的计算机（8gb内存）给出了一个没有足够内存的消息。我在另一个工具Processing中使用了相同的算法。Processing非常快，但它不能识别超过10位数的数字。我还注意到，在我生成我的计算机能够计算的质数时，打印速度很慢。

我开始在互联网上寻找解决方案，并发现将程序编译会加快进程，但我不确定它是否只会加快解释部分还是计算和打印部分也会加速。我还发现了一些关于numpy的内容，涉及数组，但我不确定这是否会显著加快我的功能。

如何更快地找到质数？

- user2784582

---

谷歌翻译给我英语到荷兰语的翻译如下：Zeef=筛子；Priemgetallen=素数；Aantal=数量；Alle priemgetallen tot="所有质数";Priemen="刺." 它做得很好吗？ :) （它纠正了我最初的语言猜测，那是德语。） - John

@Wooble 这就是筛法的思想：从所有数字开始作为候选质数，然后标记掉你知道不是质数的数字。这是算法的一个重要部分。 - Jaime

相比于https://dev59.com/vXNA5IYBdhLWcg3wPLL-#1043247，这看起来相当不错。但是对于RSA，您将使用像Miller-Rabin这样的概率测试，可能会在筛选一些关于小质数的候选者之后使用。 - starblue

这是一个精彩的主题，列出了许多计算质数及其速度的方法。它值得一读。 - Daniel

Answer 1

这是一个使用numpy的未经优化的Erathostenes筛法版本。在我的8GB笔记本电脑上运行64位Python（2.7）和Numpy（1.7）版本，它可以在不到一分钟的时间内计算出小于10^9的质数。

import numpy as np

def sieve(a):
    upper_bound = np.int(np.sqrt(a))
    is_prime = np.ones((a+1,), dtype=np.bool)
    for m in xrange(2, upper_bound+1):
        if is_prime[m]:
            is_prime[m*m::m] = False
    return np.where(is_prime)[0][2:]

>>> sieve(100)
array([ 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], dtype=int64)

以下是我的时间安排:

%timeit sieve(10**9)
1 loops, best of 3: 33.4 s per loop

%timeit sieve(10**8)
1 loops, best of 3: 2.47 s per loop

%timeit sieve(10**7)
1 loops, best of 3: 207 ms per loop

%timeit sieve(10**6)
100 loops, best of 3: 7.47 ms per loop

%timeit sieve(10**5)
1000 loops, best of 3: 716 us per loop

如果从筛子中删除所有偶数，您可以使其运行速度快两倍左右，但即使如此，在世界上拥有所有内存的情况下，您仍需要几分钟才能获得所有小于10^10的质数。

- Jaime

Answer 2

你需要一个比埃拉托色尼筛法更好的算法，如果你想生成RSA算法所需的大质数。以下是Python的Miller-Rabin素性检查器的实现：

def isPrime(n):
    def isSpsp(n, a):
        d, s = n - 1, 0
        while d % 2 == 0: d, s = d / 2, s + 1
        t = pow(a, d, n)
        if t == 1: return True
        while s > 0:
            if t == n - 1: return True
            t, s = (t * t) % n, s - 1
        return False
    ps = [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]
    if n in ps: return True
    for p in ps:
        if not isSpsp(n, p): return False
    return True

如果您对使用质数进行编程感兴趣，我谦虚地推荐阅读我博客上的文章; 您还可以查看我的其他页面，包括这篇文章关于生成RSA半素数。

- user448810

---

我发现我的算法受到了RAM的限制。由于我的数组必须包含10^8个值，这就是我的计算机无法处理的原因，因为它只有8GB的RAM。如果我想生成大质数（10^8+），埃拉托斯特尼筛法实际上是低效的。如果我计算出所有小于10^7的质数，我可以通过将检查数字除以筛选出的所有质数来检查一个整数是否为质数。我可以用这种方法找到最多10^14个质数。我对于难以快速找到大于10^9的质数的事实正确吗？ - user2784582

不需要。要快速找到一个大质数，将一个奇数输入到上述的isPrime函数中。如果它返回True，你就完成了。如果它返回False，则将该数字加2并再次尝试。找到一个质数不应该花费太长时间。Miller-Rabin算法应该能够每秒检查几百个数字。 - user448810

顺便说一下，你可以筛选高于10^7的数。诀窍是预先计算筛选素数，然后在适合内存的段中运行筛选器。请参见https://dev59.com/sWkv5IYBdhLWcg3w71L7以获取解释和代码。如果你聪明的话，甚至可以筛选非常大的数字，比如10^50或更大；请查看我的博客上的这篇文章post了解详情。 - user448810

Answer 3

你在谈论计算复杂性的一个问题。对于某些问题，即使您的处理器或编译器速度有多快，也会出现无法加速算法的情况。例如，如果您尝试解决NP完全问题，对于小的值很容易，但对于大的值则很难。

我建议您改进代码，即使您不想这样做。或者找一个能够自行处理质数生成的库。这是一个有趣的链接：http://rebrained.com/?p=458

这似乎是一个生成质数的相当不错的代码......但它也不能生成大质数（我在我的非常快的iMac上尝试过）。它在大约100000范围内很快。我建议查看此SO问题，以了解如何测试随机生成的大数字是否为素数的见解。

- user520415