用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个质数。
寻找因素的解决方案:
def divisors(integer):
result = set()
i = 2
j = integer/2
while(i <= j):
if integer % i == 0:
result.add(i)
#it dont need to
result.add(integer//i)
i += 1
j = integer//i
if len(result) > 0:
return f"not prime {sorted(result)}"
else:
return f"{integer} is prime"
—测试---- 导入的时间
start_time = time.time()
print(divisors(180180180180))
print("--- %s seconds ---" % (time.time() - start_time))
——0.06314539909362793秒——
start_time = time.time()
print(divs(180180180180180))
print("--- %s seconds ---" % (time.time() - start_time))
——1.5997519493103027秒——
start_time = time.time()
print(divisors(1827))
print("--- %s seconds ---" % (time.time() - start_time))
——0.0秒——
start_time = time.time()
print(divisors(104729))
print("--- %s seconds ---" % (time.time() - start_time))
——0.0秒——
下面的代码:
def divs(integer):
result = set()
i = 2
j = integer / 2
loops = 0
while (i <= j):
if integer % i == 0:
print(f"loops:{loops}")
return f"{integer} is not a prime"
i += 1
j = integer // i
loops += 1
print(f"loops:{loops}")
return f"{integer} is prime"
——测试——
start_time = time.time()
print(divs(180180180180180180180180))
print("--- %s seconds ---" % (time.time() - start_time))
——0.0秒——
另一个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，或者硬编码更多质数，但我想保持简单。
*示例运行时比较(注意:我使用了其他实现的优化形式，见我的评论):
这是找到从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;
}
我最近写了这段代码来求数字的和。它可以很容易地修改，以确定一个数字是否是质数。基准测试在代码之上。
// 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);
}
