用c++找出质数最快的算法是什么?我已经使用了sieve的算法,但我仍然希望它更快!
当前回答
另一个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,或者硬编码更多质数,但我想保持简单。
*示例运行时比较(注意:我使用了其他实现的优化形式,见我的评论):
其他回答
寻找因素的解决方案:
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秒——
这是找到从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;
}
我会让你决定这是不是最快的。
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个质数。
我总是用这种方法来计算筛子算法后面的质数。
void primelist()
{
for(int i = 4; i < pr; i += 2) mark[ i ] = false;
for(int i = 3; i < pr; i += 2) mark[ i ] = true; mark[ 2 ] = true;
for(int i = 3, sq = sqrt( pr ); i < sq; i += 2)
if(mark[ i ])
for(int j = i << 1; j < pr; j += i) mark[ j ] = false;
prime[ 0 ] = 2; ind = 1;
for(int i = 3; i < pr; i += 2)
if(mark[ i ]) ind++; printf("%d\n", ind);
}
#include <iostream>
using namespace std;
int set [1000000];
int main (){
for (int i=0; i<1000000; i++){
set [i] = 0;
}
int set_size= 1000;
set [set_size];
set [0] = 2;
set [1] = 3;
int Ps = 0;
int last = 2;
cout << 2 << " " << 3 << " ";
for (int n=1; n<10000; n++){
int t = 0;
Ps = (n%2)+1+(3*n);
for (int i=0; i==i; i++){
if (set [i] == 0) break;
if (Ps%set[i]==0){
t=1;
break;
}
}
if (t==0){
cout << Ps << " ";
set [last] = Ps;
last++;
}
}
//cout << last << endl;
cout << endl;
system ("pause");
return 0;
}