C++ 哪个是查找素数最快的算法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/453793/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Which is the fastest algorithm to find prime numbers?
提问by kasperasky
Which is the fastest algorithm to find out prime numbers using C++? I have used sieve's algorithm but I still want it to be faster!
使用 C++ 找出素数的最快算法是什么？我已经使用过筛的算法，但我仍然希望它更快！
回答by Greg Hewgill
A very fast implementation of the Sieve of Atkinis Dan Bernstein's primegen. This sieve is more efficient than the Sieve of Eratosthenes. His page has some benchmark information.
回答by Georg Sch?lly
If it has to be really fast you can include a list of primes:
http://www.bigprimes.net/archive/prime/
如果它必须非常快，您可以包含一个素数列表：http:
//www.bigprimes.net/archive/prime/
If you just have to know if a certain number is a prime number, there are various prime tests listed on wikipedia. They are probably the fastest method to determine if large numbers are primes, especially because they can tell you if a number is nota prime.
如果您只需要知道某个数字是否为质数，那么wikipedia 上列出了各种质数测试。他们很可能以确定是否大数是素数的最快速方法，特别是因为他们可以告诉你，如果一个数是不是素数。
回答by Mack
He, he I know I'm a question necromancer replying to old questions, but I've just found this question searching the net for ways to implement efficient prime numbers tests.
他，他我知道我是一个回答旧问题的死灵法师，但我刚刚发现这个问题在网上搜索实现有效素数测试的方法。
Until now, I believe that the fastest prime number testing algorithm is Strong Probable Prime (SPRP). I am quoting from Nvidia CUDA forums:
到目前为止，我认为最快的素数测试算法是强概率素数（SPRP）。我引用了 Nvidia CUDA 论坛：
One of the more practical niche problems in number theory has to do with identification of prime numbers. Given N, how can you efficiently determine if it is prime or not? This is not just a thoeretical problem, it may be a real one needed in code, perhaps when you need to dynamically find a prime hash table size within certain ranges. If N is something on the order of 2^30, do you really want to do 30000 division tests to search for any factors? Obviously not.
The common practical solution to this problem is a simple test called an Euler probable prime test, and a more powerful generalization called a Strong Probable Prime (SPRP). This is a test that for an integer N can probabilistically classify it as prime or not, and repeated tests can increase the correctness probability. The slow part of the test itself mostly involves computing a value similar to A^(N-1) modulo N. Anyone implementing RSA public-key encryption variants has used this algorithm. It's useful both for huge integers (like 512 bits) as well as normal 32 or 64 bit ints.
The test can be changed from a probabilistic rejection into a definitive proof of primality by precomputing certain test input parameters which are known to always succeed for ranges of N. Unfortunately the discovery of these "best known tests" is effectively a search of a huge (in fact infinite) domain. In 1980, a first list of useful tests was created by Carl Pomerance (famous for being the one to factor RSA-129 with his Quadratic Seive algorithm.) Later Jaeschke improved the results significantly in 1993. In 2004, Zhang and Tang improved the theory and limits of the search domain. Greathouse and Livingstone have released the most modern results until now on the web, at http://math.crg4.com/primes.html, the best results of a huge search domain.
数论中更实用的利基问题之一与素数的识别有关。给定 N，你如何有效地确定它是否是素数？这不仅仅是一个理论问题，它可能是代码中真正需要的问题，也许是当您需要在某些范围内动态查找素数哈希表大小时。如果 N 是 2^30 的数量级，您真的要进行 30000 次除法测试来搜索任何因子吗？显然不是。
此问题的常见实际解决方案是称为 Euler probable prime test 的简单测试，以及称为 Strong Probable Prime (SPRP) 的更强大的泛化。这是一个测试，对于整数 N 可以概率性地将其分类为素数与否，重复测试可以增加正确概率。测试本身的缓慢部分主要涉及计算类似于 A^(N-1) 模 N 的值。任何实现 RSA 公钥加密变体的人都使用过这种算法。它对大整数（如 512 位）以及普通 32 或 64 位整数都很有用。
通过预先计算某些已知在 N 范围内总是成功的测试输入参数，可以将测试从概率拒绝更改为确定的素性证明。不幸的是，这些“最知名测试”的发现实际上是对巨大（实际上是无限）域。1980 年，Carl Pomerance（因使用 Quadratic Seive 算法分解 RSA-129 而闻名）创建了第一个有用测试列表。后来 Jaeschke 在 1993 年显着改进了结果。2004 年，Zhang 和 Tang 改进了理论和搜索域的限制。Greathouse 和 Livingstone 在网络上发布了迄今为止最现代的结果，网址为http://math.crg4.com/primes.html，这是一个巨大搜索域的最佳结果。
See here for more info: http://primes.utm.edu/prove/prove2_3.htmland http://forums.nvidia.com/index.php?showtopic=70483
请参阅此处了解更多信息：http: //primes.utm.edu/prove/prove2_3.html和http://forums.nvidia.com/index.php?showtopic=70483
If you just need a way to generate very big prime numbers and don't care to generate all prime numbers < an integer n, you can use Lucas-Lehmer test to verify Mersenne prime numbers. A Mersenne prime number is in the form of 2^p -1. I think that Lucas-Lehmer test is the fastest algorithm discovered for Mersenne prime numbers.
如果您只需要一种生成非常大的素数的方法，而不关心生成所有 < 整数 n 的素数，您可以使用 Lucas-Lehmer 检验来验证梅森素数。梅森素数的形式为 2^p -1。我认为 Lucas-Lehmer 检验是为梅森素数发现的最快算法。
And if you not only want to use the fastest algorithm but also the fastest hardware, try to implement it using Nvidia CUDA, write a kernel for CUDA and run it on GPU.
如果您不仅想使用最快的算法，还想使用最快的硬件，请尝试使用 Nvidia CUDA 来实现它，为 CUDA 编写一个内核并在 GPU 上运行它。
You can even earn some money if you discover large enough prime numbers, EFF is giving prizes from $50K to $250K: https://www.eff.org/awards/coop
如果您发现足够大的质数，您甚至可以赚到一些钱，EFF 提供的奖金从 5 万美元到 25 万美元不等：https: //www.eff.org/awards/coop
回答by Kousha
There is a 100% mathematical test that will check if a number Pis prime or composite, called AKS Primality Test.
有一个 100% 数学测试将检查一个数字P是素数还是合数，称为AKS 素数测试。
The concept is simple: given a number P, if all the coefficients of (x-1)^P - (x^P-1)are divisible by P, then Pis a prime number, otherwise it is a composite number.
概念很简单：给定一个数P，如果 的所有系数(x-1)^P - (x^P-1)都可以被 整除P，P则为素数，否则为合数。
For instance, given P = 3, would give the polynomial:
例如，给定P = 3，将给出多项式：
(x-1)^3 - (x^3 - 1)
= x^3 + 3x^2 - 3x - 1 - (x^3 - 1)
= 3x^2 - 3x
And the coefficients are both divisible by 3, therefore the number is prime.
并且系数都可以被 整除3，因此这个数是素数。
And example where P = 4, which is NOT a prime would yield:
和示例 where P = 4，这不是素数会产生：
(x-1)^4 - (x^4-1)
= x^4 - 4x^3 + 6x^2 - 4x + 1 - (x^4 - 1)
= -4x^3 + 6x^2 - 4x
And here we can see that the coefficients 6is not divisible by 4, therefore it is NOT prime.
在这里我们可以看到系数6不能被 整除4，因此它不是素数。
The polynomial (x-1)^Pwill P+1terms and can be found using combination. So, this test will run in O(n)runtime, so I don't know how useful this would be since you can simply iterate over ifrom 0 to pand test for the remainder.
多项式(x-1)^P将P+1项并且可以使用组合找到。所以，这个测试将在O(n)运行时运行，所以我不知道这会有多大用处，因为你可以简单地i从 0迭代到p并测试余数。
回答by Christian Lindig
Is your problem to decide whether a particular number is prime? Then you need a primality test (easy). Or do you need all primes up to a given number? In that case prime sieves are good (easy, but require memory). Or do you need the prime factors of a number? This would require factorization (difficult for large numbers if you really want the most efficient methods). How large are the numbers you are looking at? 16 bits? 32 bits? bigger?
你的问题是决定一个特定的数字是否是素数吗？然后你需要一个素性测试（简单）。或者您是否需要给定数字以内的所有质数？在那种情况下，主筛是好的（简单，但需要记忆）。或者你需要一个数的质因数吗？这将需要因式分解（如果你真的想要最有效的方法，对于大数来说很难）。您正在查看的数字有多大？16位？32位？大？
One clever and efficient way is to pre-compute tables of primes and keep them in a file using a bit-level encoding. The file is considered one long bit vector whereas bit n represents integer n. If n is prime, its bit is set to one and to zero otherwise. Lookup is very fast (you compute the byte offset and a bit mask) and does not require loading the file in memory.
一种聪明而有效的方法是预先计算素数表，并使用位级编码将它们保存在文件中。该文件被认为是一个长位向量，而位 n 代表整数 n。如果 n 是素数，则其位设置为 1，否则设置为 0。查找速度非常快（您计算字节偏移量和位掩码）并且不需要将文件加载到内存中。
回答by Jason S
Rabin-Milleris a standard probabilistic primality test. (you run it K times and the input number is either definitely composite, or it is probably prime with probability of error 4-K. (a few hundred iterations and it's almost certainly telling you the truth)
Rabin-Miller是标准的概率素性检验。（你运行它 K 次，输入数字要么肯定是复合的，要么可能是素数，错误概率为 4 -K。（几百次迭代，它几乎肯定会告诉你真相）
There is a non-probabilistic (deterministic) variant of Rabin Miller.
Rabin Miller有一个非概率（确定性）变体。
The Great Internet Mersenne Prime Search(GIMPS) which has found the world's record for largest proven prime (274,207,281- 1 as of June 2017), uses several algorithms, but these are primes in special forms. However the GIMPS page above does include some general deterministic primality tests. They appear to indicate that which algorithm is "fastest" depends upon the size of the number to be tested. If your number fits in 64 bits then you probably shouldn't use a method intended to work on primes of several million digits.
在互联网梅森素数大搜索已找到了世界对大探明黄金记录（GIMPS）（2 74207281- 1 6月2017），采用多种算法，但这些都是特殊形式的素数。然而，上面的 GIMPS 页面确实包含了一些通用的确定性素性测试。它们似乎表明哪种算法“最快”取决于要测试的数字的大小。如果您的数字适合 64 位，那么您可能不应该使用旨在处理数百万位素数的方法。
回答by Svante
It depends on your application. There are some considerations:
这取决于您的应用程序。有一些考虑：
- Do you need just the information whether a few numbers are prime, do you need all prime numbers up to a certain limit, or do you need (potentially) all prime numbers?
- How big are the numbers you have to deal with?
- 您是否只需要一些数字是否为质数的信息，您是否需要达到某个限制的所有质数，或者您是否需要（可能）所有质数？
- 您必须处理的数字有多大？
The Miller-Rabin and analogue tests are only faster than a sieve for numbers over a certain size (somewhere around a few million, I believe). Below that, using a trial division (if you just have a few numbers) or a sieve is faster.
Miller-Rabin 和模拟测试仅比筛选特定大小的数字（我相信大约几百万左右）快。在此之下，使用试除法（如果您只有几个数字）或筛子会更快。
回答by Tayyab Mazhar
I will let you decide if it's the fastest or not.
我会让你决定它是否是最快的。
using System;
namespace PrimeNumbers
{
public static class Program
{
static int primesCount = 0;
public static void Main()
{
DateTime startingTime = DateTime.Now;
RangePrime(1,1000000);
DateTime endingTime = DateTime.Now;
TimeSpan span = endingTime - startingTime;
Console.WriteLine("span = {0}", span.TotalSeconds);
}
public static void RangePrime(int start, int end)
{
for (int i = start; i != end+1; i++)
{
bool isPrime = IsPrime(i);
if(isPrime)
{
primesCount++;
Console.WriteLine("number = {0}", i);
}
}
Console.WriteLine("primes count = {0}",primesCount);
}
public static bool IsPrime(int ToCheck)
{
if (ToCheck == 2) return true;
if (ToCheck < 2) return false;
if (IsOdd(ToCheck))
{
for (int i = 3; i <= (ToCheck / 3); i += 2)
{
if (ToCheck % i == 0) return false;
}
return true;
}
else return false; // even numbers(excluding 2) are composite
}
public static bool IsOdd(int ToCheck)
{
return ((ToCheck % 2 != 0) ? true : false);
}
}
}
It takes approximately 82 secondsto find and print prime numbers within a range of 1 to 1,000,000, on my Core 2 Duo laptop with a 2.40 GHz processor. And it found 78,498prime numbers.
在配备 2.40 GHz 处理器的 Core 2 Duo 笔记本电脑上，查找和打印 1 到 1,000,000 范围内的质数大约需要82 秒。它发现了78,498 个素数。
回答by Osman Goni Nahid
I always use this method for calculating primes numbers following with the sieve algorithm.
我总是使用这种方法来计算筛选算法之后的素数。
void primelist()
{
for(int i = 4; i < pr; i += 2) mark[ i ] = false;
for(int i = 3; i < pr; i += 2) mark[ i ] = true; mark[ 2 ] = true;
for(int i = 3, sq = sqrt( pr ); i < sq; i += 2)
if(mark[ i ])
for(int j = i << 1; j < pr; j += i) mark[ j ] = false;
prime[ 0 ] = 2; ind = 1;
for(int i = 3; i < pr; i += 2)
if(mark[ i ]) ind++; printf("%d\n", ind);
}
回答by Sushant
I don't know about any predefined algorithm but I created my own which is very fast. It can process 20 digits numbers in less than 1 seconds. The max capability of this program is 18446744073709551615. The program is :
我不知道任何预定义算法，但我创建了自己的算法，速度非常快。它可以在不到 1 秒的时间内处理 20 位数字。该程序的最大容量为 18446744073709551615。该程序为：
#include <iostream>
#include <cmath>
#include <stdlib.h>
using namespace std;
unsigned long long int num = 0;
bool prime() {
if (num % 2 == 0 || num == 1) {
return false;
}
unsigned long int square_root = sqrt(num);
for (unsigned long int i = 3; i <= square_root; i += 2) {
if (num % i == 0) {
return false;
}
}
return true;
}
int main() {
do {
system("cls");
cout << "Enter number : ";
cin >> num;
if (prime()) {
cout << "The number is a prime number" << endl << endl << endl << endl;
} else {
cout << "The number is not a prime number" << endl << endl << endl << endl;
}
system("pause");
} while (1);
return 0;
}
