c语言求素数个数,优化方法

以下是题目和我写的代码,但是超时了,谁有更优化的方法吗,求解

/*给定两个非负整数a,b,其中0<= a,b<=1,000,000,请计算这两个数之间有多少个素数。
输入
第一行是一个整数K(1<=K<=1000),表示有多少个样例,每个样例占一行,是两个整数a和b,每个整数之间用一个空格隔开。
输出
每行输出一个样例的结果。
Sample Input
2
2 3
17 19
Sample Output
2
2*/

#include
#include
int main()
{
int n,i,j,a,b,sq;
scanf("%d",&n);
while(n--)
{
int sum=0;
scanf("%d %d",&a,&b);
if(a>b)
{
int temp=a;
a=b;
b=temp;
}
for(i=a;i<=b;i++)
{
sq=sqrt(i);
for(j=2;j<=sq;j++)
if(i%j==0)
break;
if(j>sq)
sum++;
}
if(a==1||a==0)
sum--;
printf("%d\n",sum);
}
return 0;
}

3个回答

素数优化算法http://blog.csdn.net/liukehua123/article/details/5482854

 #include<stdio.h>
#include<math.h>
#define N 10000001
bool prime[N];
int main()
{
   int i, j;
   for(i=2; i<N; i++)
  if(i%2) prime[i]=true;
  else prime[i]=false;
   for(i=3; i<=sqrt(N); i++)
   {   if(prime[i])
       for(j=i+i; j<N; j+=i) prime[i]=false;
   }
   for(i=2; i<100; i++)//由于输出将占用太多io时间,所以只输出2-100内的素数。可以把100改为N
    if( prime[i] )printf("%d ",i);

   return 0;
}

先打表吧,搞一个判断素数的程序,判断出0到1000000之间的全部素数,然后把这些值输出到一个文件里,从文件里把结果拷出来,手动建数组,然后直接查询即可,这样省去了判断素数的时间,效率立刻就提高了

如果判断到n的素数,只要for(i=2;i<√n;i++)判断到根号n就行了

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐