用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,或者硬编码更多质数,但我想保持简单。
*示例运行时比较(注意:我使用了其他实现的优化形式,见我的评论):
其他回答
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.
你的问题是判断一个特定的数字是否是质数吗?然后你需要一个质数测试(很简单)。或者你需要一个给定数字之前的所有质数吗?在这种情况下,素筛是很好的(简单,但需要内存)。或者你需要一个数的质因数?这将需要分解(如果你真的想要最有效的方法,对于较大的数字很难)。你看到的数字有多大?16位?32位?更大的吗?
一种聪明而有效的方法是预先计算质数表,并使用位级编码将它们保存在文件中。文件被认为是一个长位向量,而位n表示整数n。如果n是素数,则其位设置为1,否则为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,或者硬编码更多质数,但我想保持简单。
*示例运行时比较(注意:我使用了其他实现的优化形式,见我的评论):
#include<stdio.h>
main()
{
long long unsigned x,y,b,z,e,r,c;
scanf("%llu",&x);
if(x<2)return 0;
scanf("%llu",&y);
if(y<x)return 0;
if(x==2)printf("|2");
if(x%2==0)x+=1;
if(y%2==0)y-=1;
for(b=x;b<=y;b+=2)
{
z=b;e=0;
for(c=2;c*c<=z;c++)
{
if(z%c==0)e++;
if(e>0)z=3;
}
if(e==0)
{
printf("|%llu",z);
r+=1;
}
}
printf("|\n%llu outputs...\n",r);
scanf("%llu",&r);
}
我会让你决定这是不是最快的。
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个质数。