sinat_36204309 2016-10-06 07:51 采纳率: 28.6%
浏览 4399

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条回答

  • 当作看不见 2016-10-06 08:13
    关注

    素数优化算法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;
    }
    
    评论

报告相同问题?

悬赏问题

  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥85 maple软件,solve求反函数,出现rootof怎么办?
  • ¥15 求chat4.0解答一道线性规划题,用lingo编程运行,第一问要求写出数学模型和lingo语言编程模型,第二问第三问解答就行,我的ddl要到了谁来求了
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题