用c++找出质数最快的算法是什么?我已经使用了sieve的算法,但我仍然希望它更快!
当前回答
#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);
}
其他回答
#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);
}
一个非常快速的Atkin Sieve的实现是Dan Bernstein的primegen。这个筛子比埃拉托色尼的筛子更有效率。他的页面有一些基准测试信息。
如果它必须非常快,你可以包括一个质数列表: http://www.bigprimes.net/archive/prime/
如果你只想知道某个数是不是质数,维基百科上列出了各种质数判别法。它们可能是确定大数是否为质数的最快方法,特别是因为它们可以告诉你一个数是否为质数。
我会让你决定这是不是最快的。
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个质数。
#include<iostream>
using namespace std;
void main()
{
int num,i,j,prime;
cout<<"Enter the upper limit :";
cin>>num;
cout<<"Prime numbers till "<<num<<" are :2, ";
for(i=3;i<=num;i++)
{
prime=1;
for(j=2;j<i;j++)
{
if(i%j==0)
{
prime=0;
break;
}
}
if(prime==1)
cout<<i<<", ";
}
}