3

我已经制作了一个用于生成素数的筛子。我正在做一个关于 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 内存）提示内存不足。我在另一个工具 Processing 中使用了相同的算法。处理速度非常快，但它不能识别超过 10 位数字。我还注意到，当我生成我的计算机能够计算的素数时，打印速度很慢。

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

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

4

3 回答 3

2

这是使用 numpy 的 Erathostenes 筛子的未优化版本。在我运行 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)

这是我的时间安排：

%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。

于 2013-09-16T17:46:52.240 回答
1

You will need a better algorithm than the Sieve of Eratosthenes if you want to generate the kinds of large prime numbers needed for the RSA algorithm. Here's an implementation of the Miller-Rabin primality checker for Python:

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

If you're interested in programming with prime numbers, I modestly recommend this essay at my blog; you might also look at some of the other pages at my blog, including this one on generating RSA semi-primes.

于 2013-09-16T20:45:28.250 回答
1

您在谈论计算复杂性的问题。有一点，有某些问题，无论你的处理器或编译器有多快，你都无法加速你的算法。例如，如果您试图解决一个NP 完全问题，那么对于较小的值会很容易，但对于较大的值则很难。

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

这似乎是生成素数的好代码……但它也不会生成大素数（我在我非常快的 iMac 上尝试过）。它很快就达到了大约 100000。我建议查看这个SO question，以了解如何测试随机生成的大数的素数。

于 2013-09-16T16:39:10.963 回答