这个函数用于计算a~b含有素数的个数,但是效率太低,请帮忙改进一下或告诉一个好的方法.
#include "stdio.h"
#include<math.h>
#include<malloc.h>
struct sp
{
long int num;
struct sp *next;
};
struct sp * head;
struct sp * p,* p1,* p2;
main()
{
long int a,b,t,sum;
int i,j,k,f,g,m,n;
long int e;
double d;
d=500*sqrt(2);/*确定素数的范围*/
e=(int)d+1;
p=head=p1=p2=(struct sp *)malloc(sizeof(struct sp));
for(g=0,j=2;j<e;j++)
{ g=g+1;
if(n==1)
{head=p1;
p1->num=j;
}
else
p1->num=j;
p2->next=p1;
p2=p1;
p1=(struct sp *)malloc(sizeof(struct sp));
}/*建立连续的数字链条*/
p2->next=0;
for(p=head;p1->next!=0;p1=p1->next)
for(p2=p1->next;p2->next!=0;p=p2,p2=p2->next)
if(p2->num%p1->num==0)
{
if(p2->next==0)
p->next=0;
else
p->next=p2->next;
};/*建立含素数的链条*/
while(scanf("%ld%ld",&a,&b)==2&&a>=0&&b>=0&&a<=5e5&&b<=5e5)
{
if(a>b){ t=a;a=b;b=t;}/*使b大于a,ab范围在0~500000*/
sum=0;
if(a<=2&&b>=2)/使a从2开始*/
{ g=1;
a=2;
}
else
g=0;
for(;a<=b;a++)
{
n=0;
p=head;/*素数从头开始*/
do
{
if(p->num>=a)
break;
if(a%(p->num)==0)/*使a分别除小于a的素数*/
{
n=0;
break;
}
else
n=1;
p=p->next;
}while(p->next!=0);
if(n==1)/*是素数sum增加1*/
sum=sum+1;
}
printf("%ld\n",sum+g);
continue;
}
return 0;
}
