過(guò)去一直用的求素?cái)?shù)的方法為:
bool isPrime(const int n)
{
for(int i=2;i<=sqrt(n);i++)
if((n%i)==0)
return false;
return true;
}
但是用這種方法求從2-->n的素?cái)?shù)的話，時(shí)間復(fù)雜度高。
今天發(fā)現(xiàn)一種新的方法，效率提高了很多，其核心思想如下：
bool* prime = new bool[n];
for(int i=0;i<n;i++)
prime[i]=true;
for(int i=2;i<=sqrt(n);i++)
{
if(prime[i])
{
for(int j=i*i;j<=n;j++)
prime[j]=false;
}
}
整個(gè)測(cè)試代碼如下：
#include <iostream>
#include <string>
#include <cmath>
#include <ctime>
#include <windows.h>
using namespace std;
bool* sieve(int n)
{
bool* prime = new bool[n];
for(int i=0;i<n;i++)
prime[i]=true;
prime[0]=false;
prime[1]=false;
double maxsqrt=sqrt((double)n);
for(int i=2;i<=maxsqrt;i++)
{
if(prime[i])
{
for(int j=i*i;j<=n;j+=i)
prime[j]=false;
}
}
return prime;
}
int main(int argc,char* argv[])
{
int n;
while(1)
{
cin>>n;
if(n==0)
break;
DWORD start = timeGetTime();
for(int i=3;i<=n;i++)
{
bool flag = true;
for(int j=2;j<=sqrt(i);j++)
{
if(!(i%j))
{
flag = false;
break;
}
}
/*
if(flag)
cout<<i<<" ";
*/
}
DWORD median = timeGetTime();
bool* prime = sieve(n);
/*
for(int i=0;i<n;i++)
if(prime[i])
cout<<i<<" ";
*/
DWORD end = timeGetTime();
cout<<endl;
cout<<(median-start)<<" ms "<<(end-median)<<" ms"<<endl;
delete prime;
}
system("pause");
return 0;
}