1

我正在编写一个函数来列出某个起始值“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
4

3 回答 3

1

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

可能会有所收获isprime，具体取决于它的实施方式。这完全取决于您需要它有多准确（即是否允许 Carmichael 数字？）。

编辑：

您的编辑并没有真正解决任何问题。试试这个：

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并避免函数调用。小的优化，但是，嘿，我们已经在分裂头发了。

编辑：

如果您不能接受错误（例如 Carmichael 数字），那么您将陷入执行缓慢的问题isprime（假设它是正确的）。这是因为检查一个数是否是素数是很困难的。无论如何， Fermat s Little Theorem is a clever shortcut, butisprime 可能会使用它和额外的验证来消除错误。

你真的没有什么可以做的。如果你愿意用不同的语言重写它，那么我推荐 Haskell；它对生成数字有很好的支持，并将您的代码变成大约 3 行函数（左右）。

我不太了解matlab，无法消除一些额外的循环，但这里有更多建议：

  • 如果 matlab 可以附加到 PrimeNumbersList，请这样做而不是设置索引。这可能会更快（它在 Javascript 中）
    • 这将摆脱s变量，从而消除添加
  • 使用s代替numel（试试这个而不是上面的尝试）
于 2012-11-26T02:20:03.653 回答
1

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

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，因为它是素数，但可以被 2 整除。

由于我不知道 isPrime() 的速度，我只是编写了自己的（基于素数的简单证明）。请随时使用您的 tic/toc 进行检查。

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

于 2012-11-26T02:43:29.083 回答
0

不要遍历一组数字来测试每个数字的素数。那将是不可能的慢。您正在寻找的算法称为 Eratosthenes 的分段筛。

尽管埃拉托色尼筛法非常快，但它需要 O(n) 空间。通过在连续的段中执行筛选，这可以减少到筛选素数的 O(sqrt(n)) 加上位数组的 O(1)。在第一段，计算段内每个筛素的最小倍数，然后以正常方式将筛素的倍数标记为合数；当所有的筛选素数都用完后，该段中剩余的未标记数是素数。然后，对于下一段，每个筛分素数的最小倍数是在前一段中结束筛分的倍数，因此筛分一直持续到完成。

考虑以 20 为一组从 100 到 200 筛分的例子；5个筛选素数是3、5、7、11和13。在从100到120的第一段中，位数组有10个槽，槽0对应101，槽k对应100 + 2k - 1，槽9对应119。段中3的最小倍数是105，对应slot 2；槽 2+3=5 和 5+3=8 也是 3 的倍数。槽 2 处 5 的最小倍数是 105，槽 2+5=7 也是 5 的倍数。7 的最小倍数是 105在插槽 2 处，插槽 2+7=9 也是 7 的倍数。以此类推。

函数 primes 接受参数 lo、hi 和 delta；lo 和 hi 必须是偶数，其中 lo < hi，并且 lo 必须大于上限 (sqrt(hi))。段大小是 delta 的两倍。长度为 m 的数组 ps 包含小于 sqrt(hi) 的筛分素数，去掉 2，因为偶数被忽略，数组 qs 包含对应筛分素数当前段中最小倍数的筛位数组的偏移量。在每个段之后，lo 前进两倍 delta，因此筛位数组的索引 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。这个算法非常快；您应该能够在不到一秒的时间内生成数百万个素数。

如果你想了解更多关于素数编程的知识，我在我的博客上谦虚地推荐这篇文章。

于 2012-11-26T13:46:30.157 回答