高效算法获取两个大数之间的质数

Question

我是一名C#初学者，正在尝试编写一个应用程序以获取用户输入的两个数字之间的质数。问题是：在较大的数字范围（有效数字在1到1000000000之间）内获取质数需要很长时间，而根据我正在解决的问题，整个操作必须在短时间内完成。以下是更多解释的问题链接： SPOJ-Prime

这是我代码中负责获取质数的部分：

  public void GetPrime()
    {            
        int L1 = int.Parse(Limits[0]);
        int L2 = int.Parse(Limits[1]);

        if (L1 == 1)
        {
            L1++;
        }

        for (int i = L1; i <= L2; i++)
        {
            for (int k = L1; k <= L2; k++)
            {
                if (i == k)
                {
                    continue;
                }
                else if (i % k == 0)
                {
                    flag = false;
                    break;
                }
                else
                {
                    flag = true;
                }
            }

            if (flag)
            {
                Console.WriteLine(i);
            }
        }
    }

有更快的算法吗？ 提前感谢。

- rafael

---

可能是重复问题：https://dev59.com/unRB5IYBdhLWcg3w9b19 - György Andrasek

这两个问题其实不太一样。那个问题问的是最快的是什么，而这个问题问的是什么足够快以便在SPOJ上被接受。 - IVlad

大小是相对的。出于某种原因，我会称适合于 Int32 的每个质数为小。 - Dykam

Answer 1

我记得是这样解决这个问题的:

1. 使用埃拉托色尼筛法在数组 primes 中生成所有小于sqrt(1000000000) = ~32 000的质数。
2. 对于介于m和n之间的每个数字x，只需针对primes数组中小于或等于sqrt(x)的数字进行除法测试，以测试其是否为质数。因此，对于x = 29，您仅会测试它是否可被2、3和5整除。

检查非质数的可整除性没有意义，因为如果x可被非质数y整除，则存在一个质数p < y满足x可被p整除，因为我们可以将y写成质数的乘积。例如，12可被6整除，但6 = 2 * 3，这意味着12也可被2或3整除。通过提前生成所有需要的质数（在这种情况下很少），您显着减少了实际素性测试所需的时间。

这将被接受，不需要对筛法进行任何优化或修改，它是一个相当干净的实现。

您可以通过将筛子推广到生成区间[left, right]中的质数而更快地完成，而不是像教程和教科书通常呈现的那样在[2, right]中生成。然而，这可能会变得非常丑陋，也不是必需的。但如果有人感兴趣，请参见：

http://pastie.org/9199654 和 此链接答案。

- IVlad

---

这可能会变得相当丑陋。实际上很容易，你只需要两个筛子，一个用于范围2..sqrt(n)，另一个用于m..n。C++示例：http://pastie.org/9199654，你可以获得一个漂亮的运行时间O((n-m) log log (n-m) + sqrt(n) * log log n)。如果不交错素数查找和筛选阶段，分段筛法就不会更复杂。 - Niklas B.

@IVlad，我的措辞可能有点不准确；您确实说核心质数应该由SoE计算...我假设您确实需要SoE来处理高范围的宽范围，比如这里的“(1 <= m <= n <= 1000000000, n-m<=100000)”。 - Will Ness

@IVlad实际上，在32K以下的质数非常少，你甚至可以通过试除法找到它们，而不会有任何明显的减速。--我试过了，你是对的：TD C代码在2.65秒内AC（我的旧SoE C代码只需要0.07秒）。 - Will Ness

@WillNess - 是的，这种情况很少见，筛法根本不需要。你提到分段筛法对于那些偶然发现并感兴趣的人来说是很好的，但对于这个问题来说并不需要。感谢你取消了踩。 - IVlad

我们考虑使用筛法两次怎么样？第一次得到质数数组，然后使用第二个筛子像往常一样确定是否为质数，并将可被其整除的所有数字划去。 - Arthas

Answer 2

你做了很多不必要的除法 - 如果你知道一个数不能被3整除，那么检查它是否能被9、27等数整除就没有意义了。你应该尝试只除以这个数的潜在质因数。缓存你生成的质数集，并只检查之前的质数是否可以整除。请注意，你确实需要生成小于L1的初始质数集。

记住，没有任何一个数会有一个比它自己的平方根更大的质因数，所以你可以在那一点停止你的除法。例如，你可以在5之后停止检查数字29的潜在因子。

你还可以增加2，这样你就可以完全忽略检查偶数是否是质数（当然要特殊处理数字2）。

我曾经在面试中问过这个问题 - 作为测试，我将类似于你的实现与我描述的算法进行了比较。通过优化的算法，我可以非常快地生成数十万个质数 - 我从来没有等待过慢速、直接的实现。

- Michael

Answer 3

你可以尝试 埃拉托色尼筛法。基本区别在于你从 L1 开始，而不是从 2 开始。

- Brian S

---

我喜欢这个算法的一件事情是，你可以潜在地并行执行它，以利用多个核心 - 可惜我从来没有真正尝试过。 - Michael

哦，不，你仍然需要从2开始。 - BlueRaja - Danny Pflughoeft

Answer 4

int ceilingNumber = 1000000;
int myPrimes = 0;


BitArray myNumbers = new BitArray(ceilingNumber, true);

for(int x = 2; x < ceilingNumber; x++)
    if(myNumbers[x])
    {
        for(int y = x * 2; y < ceilingNumber; y += x)
            myNumbers[y] = false;
    }


for(int x = 2; x < ceilingNumber; x++)
    if(myNumbers[x])
    {
        myPrimes++;
        Console.Out.WriteLine(x);

    }

Console.Out.WriteLine("======================================================");

Console.Out.WriteLine("There is/are {0} primes between 0 and {1} ",myPrimes,ceilingNumber);

Console.In.ReadLine();

- Enow B. Mbi

Answer 5

让我们稍微改变一下问题：您能多快地生成介于m和n之间的质数并将它们简单地写入内存吗？（或者，可能是RAM磁盘。）另一方面，请记住问题页面上描述的参数范围：m和n可以高达十亿，而n-m最多为一百万。

即使较慢的解决方案足够好，IVlad和Brian也提供了一个竞争性的解决方案。首先生成甚至预计算小于十亿平方根的质数；它们不是很多。然后执行截断的埃拉托斯特尼筛法：创建长度为n-m+1的数组，以跟踪范围[m，n]中每个数字的状态，最初将每个这样的数字标记为质数（1）。然后对于每个预计算的质数p，执行类似以下内容的循环：

for(k=ceil(m/p)*p; k <= n; k += p) status[k-m] = 0;

这个循环将在范围m<=x<=n中的所有p的倍数标记为合数（0）。如果这就是IVlad所说的“相当丑陋”，我不同意；我认为它并不那么糟糕。

实际上，这项工作中有近40%只是为了质数2、3和5。有一个技巧可以将筛法与状态数组的初始化结合起来。也就是说，2、3和5的可整除性模30重复。你可以将数组初始化为一个重复模式010000010001010001010001000001，而不是把它初始化为全部为1的数组。如果你想更加前沿一些，你可以通过k增加30*p而不是p，并且只标记相同模式下的倍数。

此后，实现实际性能提升的步骤可能包括使用位向量而不是字符数组来将筛选数据保存在芯片缓存中。以及按字而不是按位进行位向量的初始化。这会变得比较混乱，而且还是一种假设，因为您生成质数的速度可能比使用质数的速度更快。基本的筛法已经非常快速而且并不复杂。

- Greg Kuperberg

Answer 6

有许多算法可以找到质数。有些更快，有些更简单。

您可以从一些最简单的优化开始。例如，

• 如果每个数字都是质数，为什么要搜索？换句话说，如果给定范围为411到418，是否需要搜索412、414、416和418这些数字是否为质数？可以通过非常简单的代码修改跳过除以2和3的数字。

• 如果数字不是5，但以数字“5”结尾（1405、335），它不是质数不好的想法：它会使搜索变慢。

• 缓存结果怎么样？然后您可以通过质数而不是每个数字进行除法运算。此外，只涉及小于您搜索的数字的平方根的质数。

如果您需要真正快速和优化的东西，那么使用现有算法而不是重新发明轮子可能是一种选择。您还可以尝试找到一些科学论文，解释如何快速完成，但理解并将其转换为代码可能很困难。

- Arseni Mourzenko

---

将数字转换为十进制以检查最后一位是否为5的效率明显比只检查 num % 5 == 0 慢得多... - BlueRaja - Danny Pflughoeft

Answer 7

没有人提到的一件事是，测试单个数字的素性是相当快速的。 因此，如果涉及的范围很小但数字很大（例如，在1,000,000,000和1,000,100,000之间生成所有素数），最好只是逐个检查每个数字的素性。

- BlueRaja - Danny Pflughoeft

---

我本来想提出这个观点，但后来意识到它与问题的参数无关。即使对于您给出的示例范围，该范围也足够大，筛法更快。如果您想要在1,000,000,000和1,000,001,000之间找到所有质数，那么部分筛法结合Miller-Rabin算法将是最佳选择。 - Greg Kuperberg

Answer 8

我认为我有一个非常快速和高效（即使使用BigInteger类型也可以生成所有质数）的算法来获取质数，它比任何其他算法都更快更简单，并且我用它来解决几乎所有与质数相关的Project Euler问题，只需要几秒钟就能得到完整的解决方案（暴力破解）。 以下是Java代码：

public boolean checkprime(int value){  //Using for loop if need to generate prime in a 
    int n, limit;                        
    boolean isprime;

    isprime = true;
    limit = value / 2;
    if(value == 1) isprime =false;

    /*if(value >100)limit = value/10;  // if 1 number is not prime it will generate
    if(value >10000)limit = value/100; //at lest 2 factor (not 1 or itself)
    if(value >90000)limit = value/300; // 1 greater than  average 1  lower than average
    if(value >1000000)limit = value/1000; //ex: 9997 =13*769 (average ~ sqrt(9997) is 100)
    if(value >4000000)limit = value/2000; //so we just want to check divisor up to 100
    if(value >9000000)limit = value/3000; // for prime ~10000 
    */

    limit = (int)Math.sqrt(value); //General case
    for(n=2; n <= limit; n++){
        if(value % n == 0 && value != 2){
            isprime = false;
            break;
        }
    }
    return isprime;
}

- Tranquocbinh333

---

最后为什么不直接返回 isprime 呢？ - DarthJDG

是的，这是真的，只需返回isprime即可。 - Tranquocbinh333

1百万和1000万数字之间的执行时间相差很大（例如：0.5秒与8秒）。通过将循环增量从1改为2，您可以将测试集减少一半。 - Sinaesthetic

Answer 9

import java.io.*;
import java.util.Scanner;
class Test{
public static void main(String args[]){

   Test tt=new Test();
   Scanner obj=new Scanner(System.in);
   int m,n;
      System.out.println(i);
   m=obj.nextInt();
   n=obj.nextInt();
   tt.IsPrime(n,m);
     }
   public void IsPrime(int num,int k)
   {
       boolean[] isPrime = new boolean[num+1];
       // initially assume all integers are prime
        for (int i = 2; i <= num; i++) {
            isPrime[i] = true;
        }

        // mark non-primes <= N using Sieve of Eratosthenes
        for (int i = 2; i*i <= num; i++) {

            // if i is prime, then mark multiples of i as nonprime
            // suffices to consider mutiples i, i+1, ..., N/i
            if (isPrime[i]) {
                for (int j = i; i*j <=num; j++) {
                    isPrime[i*j] = false;
                }
            }
        } 
        for (int i =k; i <= num; i++) {
            if (isPrime[i]) 
            {
                     System.out.println(i);
            }
        }

    }

}

- Anish Kumar

---

在你的内循环中应该使用加法而不是乘法：[i*j]; j++ 等价于 [j]; j+=i。 - Will Ness

Answer 10

List<int> prime(int x, int y)
    {
        List<int> a = new List<int>();
        int b = 0;
        for (int m = x; m < y; m++)
        {
            for (int i = 2; i <= m / 2; i++)
            {
                b = 0;
                if (m % i == 0)
                {
                    b = 1;
                    break;
                }
            }
            if (b == 0) a.Add(m)`
        }
      return a;
   }

- Rana Tomar

---

欢迎来到SO，请添加一些解释您的解决方案，这将增加您获得赞同的机会。 - Alejandro Montilla