优化素数函数速度

Question

我正在写一个函数来列出在特定起始值'N以上的素数'M'数。在这一点上，我只想尽可能地提高功能（即：FAST！）。我真的没有想法，所以任何帮助将不胜感激。代码（matlab）如下：

function PrimeNumbersList = primes_after(N,M) 
tic; 
x = N; 
s = 1; 
PrimeNumbersList = 0; 
if mod(N,2) == 0 
while numel(PrimeNumbersList) < M 

if isprime(x) == 1 
    PrimeNumbersList(s) = x; 
    x=x+2; 
    s=s+1; 
else 
    x=x+2; 
end 
end 
else 
while numel(PrimeNumbersList) < M 

if isprime(x) == 1 
    PrimeNumbersList(s) = x; 
    x=x+1; 
    s=s+1; 
else 
    x=x+1; 
end 
end 
end 
tElapsed=toc 
end 

Answer 1

你可以做的一件事是只考虑奇数（增加2而不是1）。这会将循环迭代次数减半。

isprime可能会有收益，取决于它的实施方式。这一切都取决于你需要的准确度（即卡迈克尔号码是否允许？）。

编辑：

你所做的修改并没有真正解决任何事情。试试这个：

function PrimeNumbersList = primes_after(N,M) 
    tic; 
    x = N; 
    s = 1; 
    PrimeNumbersList = 0; 

    if mod(x,2) == 0 
     if x == 2 
      PrimeNumbersList(s) = x; 
      s=s+1; 
     end 
     x=x+1; 
    end 

    while numel(PrimeNumbersList) < M 
     if isprime(x) == 1 
      PrimeNumbersList(s) = x; 
      s=s+1; 
     end 
     x=x+2; 
    end 

    tElapsed=toc 
end 

另外，你或许可以改变numel(PrimeNumberList) < M到s < m，避免函数调用。小的优化，但是，嘿，我们已经分裂头发。

编辑：

如果你不能接受的错误（例如卡迈克尔数），那么你坚持执行缓慢的isprime（asuming它是正确的）。这是因为检查数字是否是素数是困难的。 Fermat s Little Theorem is a clever shortcut, but isprime`无论如何都可以使用额外的验证来消除错误。

你真的没有什么可以做的。如果你愿意用不同的语言重写这个，那么我推荐Haskell;它为生成数字提供了很好的支持，并将您的代码转换为大约3行的函数（大概是这样）。

我不知道MATLAB不够好，以消除一些额外的周期，但这里有一些建议：

• 如果MATLAB可以追加到PrimeNumbersList，做到这一点，而不是设置索引。这可能会更快（这是在Javascript）
  • 这将摆脱s变量，从而消除了另外的
• 使用s代替numel（尝试，取代上述尝试这个）

Answer 2

这里有一些潜在的速度增加。

function PrimeNumbersList = primes_after(N,M) 
tic; 

x = 0; 
if (N mod 2) == 0 && N != 2 
    x = N + 1; 
else 
    x = N; 
end 

s = 1; 
PrimeNumbersList = 0; 
tempInt = x - 1; 
isPrime = 1; 

while numel(PrimeNumbersList) < M 

    while tempInt > 1 && isPrime 
     if (x mod tempInt) == 0 
      isPrime = 0; 
     end 
     tempInt=tempInt-1; 
    end 

    if isPrime 
     PrimeNumbersList(s) = x; 
     x=x+1; 
     s=s+1; 
    else 
     x=x+1; 
    end 

end 
tElapsed=toc 
end 

好了，现在的解释：

首先，我检查，看看是否N是偶数。如果是这样，我增加1只是为了确保它是奇怪的（虽然不一定是总理）。因为它是素数，但是可以被2整除。

由于我不知道isPrime（）的速度，我只写了我自己的（基于一个简单的质数证明号）。随意检查你的tic/toc。

除此之外，我看不到更多的速度增加。我的2美分。

Answer 3

做不是迭代通过一组数字测试每个素数。这将是不可能的缓慢。您正在寻找的算法被称为Eratosthenes的分割筛。

虽然Eratosthenes的筛网速度非常快，但它需要O（n）空间。对于筛选素数，可以通过在连续的片段中执行筛分将其减少到O（sqrt（n））加上O（1）的比特数。在第一个分段中，计算分段内每个筛分质数的最小倍数，然后以正常方式标记复合质量的多个筛分质数;当使用所有筛分质数时，该分段中剩余的未标记数字是质数。然后，对于下一个分段，每个筛分质数的最小倍数是在前一个分段中结束筛分的倍数，因此筛分继续直到完成。

考虑从20到200的分段筛选100到200的例子; 5个筛选素数是3,5,7,11和13.在100到120的第一段中，比特数有10个时隙，其中时隙0对应于101，时隙k对应于100 + 2k-1，时隙9对应于119.分段中的3的最小倍数是105，对应于时隙2;时隙2 + 3 = 5和5 + 3 = 8也是3的倍数。时隙2处的5的最小倍数是105，时隙2 + 5 = 7也是5的倍数.7的最小倍数是105在时隙2处，时隙2 + 7 = 9也是7的倍数。依此类推。

函数素数需要参数lo，hi和delta; lo和hi必须是偶数，并且lo必须大于天花板（sqrt（hi））。段的大小是两倍三角洲。长度为m的数组ps包含小于sqrt（hi）的筛选素数，删除2，因为偶数会被忽略，并且数组qs包含到相应筛选素数当前片段中最小倍数的筛子位阵列的偏移量。每个段之后，LO通过两次增量前进，所以对应于筛bitarray的索引j的数目为LO + 2J + 1

function primes(lo, hi, delta) 
    sieve := makeArray(0..delta-1) # bitarray 
    # calculate m and ps as described in text 
    qs := makeArray(0..m-1) # least multiples 
    for i from 0 to m-1 
    qs[i] := (-1/2 * (lo + ps[i] + 1)) % ps[i] 
    while lo < hi 
    for i from 0 to delta-1 
     sieve[i] := True 
    for i from 0 to m-1 
     for j from qs[i] to delta step ps[i] 
     sieve[j] := False 
     qs[i] := (qs[i] - delta) % ps[i] 
    for i from 0 to delta-1 
     t := lo + 2*j + 1 
     if sieve[i] and t < hi 
     output t 
    lo := lo + 2*delta 

对于上面给出的样品，这被称为质数（100， 200，10）。在上面给出的例子中，qs最初是[2,2,2,10,8]，对应于最小倍数105,105,105,121和117，并且针对第二段重置为[1,2,6， 0,11]，对应于最小倍数123,125,133,121和143。该算法非常快;你应该能够在不到一秒的时间内生成几百万个素数。

如果您想了解更多关于使用素数编程的信息，我会在我的博客上谦虚地推荐this essay。