高效的算法来获得两个大数之间的素数

我是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); } } } 

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

Answer 1

我记得像这样解决问题：

1. 使用eratosthenes的筛子在arrays质primes生成低于sqrt(1000000000) = ~32 000的所有质primes 。
2. 对于m和n之间的每个数字x ，只测试它是否为素数，通过测试数字素数<= sqrt(x)可分性。 所以对于x = 29你只会测试它是否可以分为2, 3 and 5 。

检查非素数的可除性是没有意义的，因为如果x divisible by non-prime y ，那么存在素数p < y ，使得x divisible by p ，因为我们可以将y写为素数的乘积。 例如， 12可被6整除，但6 = 2 * 3 ，这意味着12也可被2或3整除。 通过预先生成所有需要的素数（在这种情况下很少），您可以显着减少实际素性测试所需的时间。

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

你可以通过推广筛子来更快地完成它，在一个区间[left, right] ，而不是[2, right]生成素数，就像它通常在教程和教科书中一样。 然而，这可能变得非常难看，并且不需要它。 但如果有人有兴趣，请参阅：

http://pastie.org/9199654和这个相关的答案 。

Answer 2

你正在进行许多不需要的额外划分 – 如果你知道一个数字不能被3整除，那么检查它是否可以被9,27等整除是没有意义的。你应该试着只划分潜力数量的主要因素。 缓存您正在生成的素数集，并仅检查前一个素数的除法。 请注意，您需要生成低于L1的初始素数集。

请记住，没有数字的主要因子大于其自己的平方根，因此您可以在此时停止分割。 例如，您可以在5之后停止检查数字29的潜在因素。

你也可以增加2，所以你可以忽略检查一个偶数是否是完全素数（当然，特殊的套管数字2）。

我曾经在采访中提出这个问题 – 作为一项测试，我将与你的类似的实现与我描述的算法进行了比较。 通过优化算法，我可以非常快速地生成数十万个素数 – 我从不费心等待缓慢，直接的实现。

Answer 3

你可以试试Eratosthenes的Sieve 。 基本的区别在于你从L1开始而不是从2开始。

Answer 4

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

IVlad和Brian大多数都是一个有竞争力的解决方案，即使速度较慢的解决方案确实足够好也是如此。 首先生成或甚至预先计算小于sqrt（十亿）的素数; 它们不是很多。 然后做一个截断的Eratosthenes筛子：制作一个长度为n-m + 1的数组，以跟踪[m，n]范围内每个数字的状态，最初每个这样的数字都标记为素数（1）。 然后对于每个预先计算的素数p，执行如下所示的循环：

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

如果它们是p的倍数，则该循环将范围m <= x <= n中的所有数字标记为复合（0）。 如果这是IVlad所说的“非常丑陋”，我不同意; 我不认为这太糟糕了。

实际上，这项工作中有近40％只用于素数2,3和5.有一个技巧可以将几个素数的筛子与状态数组的初始化结合起来。 也就是说，可以通过2,3和5重复模式的模式30.而不是将数组初始化为全1，您可以将其初始化为重复模式010000010001010001010001000001.如果您想要更加前沿，您可以提前k乘以30 * p而不是p，并且仅以相同的模式标记倍数。

在此之后，实际的性能提升将涉及诸如使用位向量而不是char数组来将筛选数据保持在片上高速缓存中的步骤。 并逐字逐字地初始化位向量。 这确实变得混乱，也是假设的，因为你可以比你使用它们更快地生成素数。 基本筛已经非常快，并不是很复杂。

Answer 5

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

Answer 6

有许多算法可以找到素数。 有些更快，有些更容易。

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

• 你为什么要搜索每个数字是否为素数？ 换句话说，如果在411到418的范围内，您是否确定需要搜索数字412,414,416和418是否为素数？ 可以通过非常简单的代码修改跳过除以2和3的数字。

• 如果数字不是5，但以数字’5’（1405,335）结束，那不是主要的坏主意：它会使搜索变慢。

• 如何缓存结果？ 然后，您可以按素数除以每个数字。 此外，只有少于您搜索数字的平方根的素数。

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

Answer 7

 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(); 

Answer 8

 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); } } } 

}

Answer 9

我认为我有一个非常快速和有效（生成所有素数，即使使用类型BigInteger）算法来获得素数，它比任何其他更快更简单，我用它来解决与项目欧拉中素数相关的几乎问题只需几秒钟就可以完成解决方案（蛮力）这里是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; } 

Answer 10

 List prime(int x, int y) { List a = new List(); 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; }