用c++找出质数最快的算法是什么?我已经使用了sieve的算法，但我仍然希望它更快!
当前回答
我最近写了这段代码来求数字的和。它可以很容易地修改，以确定一个数字是否是质数。基准测试在代码之上。
// 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);
}
其他回答
这取决于您的应用程序。这里有一些注意事项:
你需要的仅仅是一些数字是否是质数的信息，你需要所有的质数达到一定的限度，还是你需要(潜在的)所有的质数? 你要处理的数字有多大?
米勒-拉宾和模拟测试只比筛选超过一定规模的数字(我相信大约在几百万左右)的速度快。在这以下，使用试除法(如果你只有几个数字)或筛子会更快。
我会让你决定这是不是最快的。
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/
如果你只想知道某个数是不是质数，维基百科上列出了各种质数判别法。它们可能是确定大数是否为质数的最快方法，特别是因为它们可以告诉你一个数是否为质数。
我最近写了这段代码来求数字的和。它可以很容易地修改，以确定一个数字是否是质数。基准测试在代码之上。
// 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);
}
另一个Python实现比死亡面具推销员的答案更直接，也更快:
import numpy as np
def prime_numbers(limit: int) -> list[int]:
"""Provide a list of all prime numbers <= the limit."""
is_prime = np.full((limit + 1, ), True)
is_prime[0:2] = False
for n in range(2, limit + 1):
if is_prime[n]:
is_prime[n**2::n] = False
return list(np.where(is_prime)[0])
你可以进一步优化，例如，排除2，或者硬编码更多质数，但我想保持简单。
*示例运行时比较(注意:我使用了其他实现的优化形式，见我的评论):
