使用编译使我的程序更快

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)

我确信有一种更快的方法来生成素数，但是我现在对改进我的代码并不感兴趣。在

当我运行这个函数时，它可以很好地生成7位数的素数，但是当我想要更多的时候，它就很慢了。我的电脑（8gb内存）显示内存不足。我在处理中使用了同样的算法，另一种工具。处理速度很快，但识别不到10个以上的数字。 我还注意到，当我生成计算机能够计算的素数时，打印速度很慢。在

我开始在互联网上搜索，我发现我编写的程序可以加快进度，但我不确定它是加速计算和打印部分还是只是解释部分。 我还发现了一些关于numpy-wich的关于数组的东西，但我不确定这是否会显著提高我的功能。在

怎样才能更快地找到我的素数？在

Answer 1

你说的是computational complexity的问题。到了某个时候，随着某些问题的出现，无论你的处理器或编译器有多快，你都无法加速你的算法。例如，如果您试图求解一个NP-complete problem，那么对于较小的值很容易，但是对于较大的值则很难。在

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

这似乎是生成素数的很好的代码…但它也不能生成大素数（我在我非常快的iMac上尝试过）。很快就涨到了10万左右。我建议您看看thisSO问题，了解如何测试随机生成的大数的素性。在

Answer 2

如果你想生成RSA算法所需的大素数，你需要一个比Eratosthenes筛更好的算法。下面是针对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

如果您对使用素数编程感兴趣，我在我的博客上谦虚地推荐这个essay；您也可以在我的博客上查看其他一些页面，包括关于生成RSA半素数的this one。在

Answer 3

这是一个未优化的版本，使用的是numpy。在我运行64位版本的Python（2.7）和Numpy（1.7）的8GB笔记本电脑上，它可以在一分钟内计算出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)

下面是我的时间安排：

^{pr2}$

你可以把所有的偶数从筛子里去掉，使它运行得快一倍，但是即使有了这个和世界上所有的内存，你仍然需要几分钟来得到所有的素数，直到10^10。在