何为素数,一般想到的就是不能被比他小的数所能整除的数,再进一步想,不能被比他的一半小的数所能整除的数,再进一步,不能被比他的平方根小的数所能整除,能否再优化呢?答案是肯定的,如果一个数不能被比他小的所有素数整除,这个数就是素数,这是素数真正的定义,只要考虑素数就可以了,和上面的结合起来就是如果这个数不有被比他的平方根小的所有素数整除,这个数就是素数.下面是我曾经写的一个程序,用来求m到n之间的素数个数,n小于1000000,如果要更大,就将N改大点,数组a再定义大点即可,求0到1000000的所有素数个数可在一秒内得到结果.
#include<stdio.h>
#include<math.h>
#include<time.h>
#define N 1000
int a[168]={2};
void init(void) //求出1000以内的所有素数,储存在数组中
{
int i,j,k=1,sure=1;
for(j=3;j<N;j++)
{
for(i=2;i<=sqrt(j);i++)
if(j%i==0)
{
sure=0;
break;
}
if(sure)
a[k++]=j;
sure=1;
}
}
int prime(long n) //判断该数是否为素数
{
int i;
if(n<2)
return 0;
if(n==2)
return 1;
for(i=0;i<168;i++)
{
if(a[i]>sqrt(n))
break;
if(n%a[i]==0)
return 0;
}
return 1;
}
int main(void)
{
long m,n,i;
clock_t start,over; // 定义两个变量用来储存时间
int sum;
while(scanf("%ld",&n))
{
start=clock(); //记录起始时间
init();
sum=1;
for(i=3;i<=n;i+=2)
if(prime(i))
sum++;
printf("%d\n",sum);
over=clock(); //记录结束时间
printf("消耗时间:%lfms\n",(double)(over-start)); //输出程序运行时间
}
return 0;
}
以上是为了节约空间.如果你认为空间足够大,那么用以下方法即可高效的得到结果(就是所为的筛法求0到1000000内的素数个数,本机测试只需125MS左右,0到10000000内的要1391MS,如果想求更大的,只要将N改得更大即可,不过也有范围,最大值可能与机器有关)
#include<stdio.h>
#include<time.h>
#define N 10000000
int a[N];
void prime(long n) //用筛法将不是素数的值置0
{
long i,j;
a[1]=0;
for(i=2;i<n;i++)
a[i]=1;
for(i=2;i<n/2;i++)
if(a[i])
for(j=i*2;j<n;j=j+i)
a[j]=0;
}
int main()
{
int m,n,sum,i;
clock_t start,finish;
while(scanf("%d",&n))
{
start=clock();
prime(n);
sum=1;
for(i=3;i<=n;i++)
if(a[i])
sum++;
printf("%d\n",sum);
finish=clock();
printf("%lf\n",(double)(finish-start));
}
return 0;
}
为了让程序消耗内存更少,由于数组中储存的只是1和0,所以用最小的储存类型储存,所以我用C++改为bool型(另一种更优的办法是用位段来处理),另外不用储存偶数的情况,所以对比INT(32位)内在减少了8倍,而在效率上我也优化了3倍左右,具体程序如下:
#include<iostream>
#include<time.h>
#define N 100000000
bool a[N];
using namespace std;
void prime(unsigned long n) //用筛法将不是素数的值置0
{
unsigned long i,j;
a[0]=1; //2是唯一的偶素数,另作打算
for(i=3;i<=n;i+=2) //将大于2小于或等于n的奇数
a[i/2]=1;
for(i=3;i<=n/3;i+=2) //只要考虑小于n/3的就可以了,因为乘以2就是偶数,至少也是乘以3,
大于n/3的就不用判断
{
if(a[i/2])
for(j=i*3;j<=n;j+=2*i) //j的奇数倍的数全部筛选出去
a[j/2]=0;
}
}
int main()
{
unsigned long n,sum,i;
clock_t start,finish;
while(scanf("%d",&n))
{
start=clock();
prime(n);
sum=1;
for(i=3;i<=n;i+=2)
if(a[i/2])
sum++;
cout<<"the number of the prime less than n is "<<sum<<endl;
finish=clock();
cout<<"the promgram expends "<<(double)(finish-start)<<"ms"<<endl;
}
return 0;
}
如果有更优的算法,希望分享一下
[此贴子已经被作者于2007-8-29 8:15:16编辑过]
