用c++找出质数最快的算法是什么?我已经使用了sieve的算法，但我仍然希望它更快!
当前回答
寻找因素的解决方案:
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秒——
其他回答
寻找因素的解决方案:
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秒——
I know it's somewhat later, but this could be useful to people arriving here from searches. Anyway, here's some JavaScript that relies on the fact that only prime factors need to be tested, so the earlier primes generated by the code are re-used as test factors for later ones. Of course, all even and mod 5 values are filtered out first. The result will be in the array P, and this code can crunch 10 million primes in under 1.5 seconds on an i7 PC (or 100 million in about 20). Rewritten in C it should be very fast.
var P = [1, 2], j, k, l = 3
for (k = 3 ; k < 10000000 ; k += 2)
{
loop: if (++l < 5)
{
for (j = 2 ; P[j] <= Math.sqrt(k) ; ++j)
if (k % P[j] == 0) break loop
P[P.length] = k
}
else l = 0
}
一个非常快速的Atkin Sieve的实现是Dan Bernstein的primegen。这个筛子比埃拉托色尼的筛子更有效率。他的页面有一些基准测试信息。
我最近写了这段代码来求数字的和。它可以很容易地修改，以确定一个数字是否是质数。基准测试在代码之上。
// 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);
}
Rabin-Miller是一个标准的概率质数检验。(你运行K次，输入数字要么肯定是合数，要么可能是素数，误差概率为4-K。(经过几百次迭代，它几乎肯定会告诉你真相)
拉宾·米勒有一个非概率(确定性)的变体。
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.
