用c++找出质数最快的算法是什么?我已经使用了sieve的算法,但我仍然希望它更快!
当前回答
#include<iostream>
using namespace std;
void main()
{
int num,i,j,prime;
cout<<"Enter the upper limit :";
cin>>num;
cout<<"Prime numbers till "<<num<<" are :2, ";
for(i=3;i<=num;i++)
{
prime=1;
for(j=2;j<i;j++)
{
if(i%j==0)
{
prime=0;
break;
}
}
if(prime==1)
cout<<i<<", ";
}
}
其他回答
我会让你决定这是不是最快的。
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个质数。
这是找到从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;
}
一个非常快速的Atkin Sieve的实现是Dan Bernstein的primegen。这个筛子比埃拉托色尼的筛子更有效率。他的页面有一些基准测试信息。
如果它必须非常快,你可以包括一个质数列表: http://www.bigprimes.net/archive/prime/
如果你只想知道某个数是不是质数,维基百科上列出了各种质数判别法。它们可能是确定大数是否为质数的最快方法,特别是因为它们可以告诉你一个数是否为质数。
我最近写了这段代码来求数字的和。它可以很容易地修改,以确定一个数字是否是质数。基准测试在代码之上。
// built on core-i2 e8400
// Benchmark from PowerShell
// Measure-Command { ExeName.exe }
// Days : 0
// Hours : 0
// Minutes : 0
// Seconds : 23
// Milliseconds : 516
// Ticks : 235162598
// TotalDays : 0.00027217893287037
// TotalHours : 0.00653229438888889
// TotalMinutes : 0.391937663333333
// TotalSeconds : 23.5162598
// TotalMilliseconds : 23516.2598
// built with latest MSVC
// cl /EHsc /std:c++latest main.cpp /O2 /fp:fast /Qpar
#include <cmath>
#include <iostream>
#include <vector>
inline auto prime = [](std::uint64_t I, std::vector<std::uint64_t> &cache) -> std::uint64_t {
std::uint64_t root{static_cast<std::uint64_t>(std::sqrtl(I))};
for (std::size_t i{}; cache[i] <= root; ++i)
if (I % cache[i] == 0)
return 0;
cache.push_back(I);
return I;
};
inline auto prime_sum = [](std::uint64_t S) -> std::uint64_t {
std::uint64_t R{5};
std::vector<std::uint64_t> cache;
cache.reserve(S / 16);
cache.push_back(3);
for (std::uint64_t I{5}; I <= S; I += 8)
{
std::uint64_t U{I % 3};
if (U != 0)
R += prime(I, cache);
if (U != 1)
R += prime(I + 2, cache);
if (U != 2)
R += prime(I + 4, cache);
R += prime(I + 6, cache);
}
return R;
};
int main()
{
std::cout << prime_sum(63210123);
}