用c++找出质数最快的算法是什么?我已经使用了sieve的算法,但我仍然希望它更快!
当前回答
如果它必须非常快,你可以包括一个质数列表: http://www.bigprimes.net/archive/prime/
如果你只想知道某个数是不是质数,维基百科上列出了各种质数判别法。它们可能是确定大数是否为质数的最快方法,特别是因为它们可以告诉你一个数是否为质数。
其他回答
有一个100%的数学测试可以检查一个数字P是质数还是合数,叫做AKS质数测试。
概念很简单:给定一个数字P,如果(x-1)^P - (x^P-1)的所有系数都能被P整除,那么P是一个质数,否则它是一个合数。
例如,给定P = 3,会给出多项式:
(x-1)^3 - (x^3 - 1)
= x^3 + 3x^2 - 3x - 1 - (x^3 - 1)
= 3x^2 - 3x
系数都能被3整除,所以这个数是素数。
P = 4不是质数的例子是:
(x-1)^4 - (x^4-1)
= x^4 - 4x^3 + 6x^2 - 4x + 1 - (x^4 - 1)
= -4x^3 + 6x^2 - 4x
这里我们可以看到系数6不能被4整除,因此它不是质数。
多项式(x-1)^P有P+1项,可以用组合法找到。因此,这个测试将在O(n)个运行时间内运行,所以我不知道这有多有用,因为你可以简单地从0到p遍历I,然后测试剩余的部分。
一个非常快速的Atkin Sieve的实现是Dan Bernstein的primegen。这个筛子比埃拉托色尼的筛子更有效率。他的页面有一些基准测试信息。
我会让你决定这是不是最快的。
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);
}
}
}
在我使用2.40 GHz处理器的酷睿2 Duo笔记本电脑上,查找并打印1到1,000,000范围内的质数大约需要82秒。它找到了78,498个质数。
如果它必须非常快,你可以包括一个质数列表: http://www.bigprimes.net/archive/prime/
如果你只想知道某个数是不是质数,维基百科上列出了各种质数判别法。它们可能是确定大数是否为质数的最快方法,特别是因为它们可以告诉你一个数是否为质数。
这是找到从1到n的所有质数的最快算法(在我的电脑上,它只花了0.004秒就找到了从1到1000000的所有质数)。
#include <iostream>
#include <fstream>
using namespace std;
double FindPrime(bool* array, int size){
clock_t start;
double runtime;
for (int i = 2; i < size; i++)
array[i] = true;
start = clock();
for (int i = 2; i <= size; i++)
if (array[i])
for (int j = 2 * i; j < size; j += i)
array[j] = false;
runtime = (double)(clock() - start) / CLOCKS_PER_SEC;
return runtime;
}
int main() {
ofstream fout("prime.txt");
int n = 0;
cout << "Enter the upper limit of prime numbers searching algorithm:";
cin >> n;
bool* array = new bool[n + 1];
double duration = FindPrime(array, n + 1);
printf("\n%f seconds.\n", duration);
for (int i = 2; i <= n; i++)
if (array[i])
fout << i << endl;
fout.close();
return 0;
}