我的算法不对

拖延症晚期来报道：
/* 按照我之前的思路做，只能先求出1~a之间的素数个数，再求出1~b之间的素数个数，然后将两者相减得到结果，这样做将1~a之间的过程
重复计算了两次，不是很好
换一种思路是利用筛法先将所有素数球出来，然后再判断a~b之间有多少个素数
*/
第一种求法：
#include <stdio.h>
#include <math.h>

int c[1000001];
int main()
{
    int K,i,j,t;//k是案例个数
    int a,b;
    scanf("%d",&K);

    //输入a和b的值
    while(K--)
    {
         //用筛法把非素数都赋值成0.
         int t,num1=0,num2=0;
         scanf("%d %d",&a,&b);
         for(i=2; i<=a; i++)//对数组进行初始化
        {
            c[i] = i;
        }        
        for(i=2; i<=sqrt(a); i++)//进行筛选
        {
            
            for(j=i+1; j<=a; j++)
            {
                if(c[i]!=0 && c[j]!=0 && c[j]%c[i]==0)
                {
                    c[j]=0;
                }
            }
        }

        for(i=2; i<=a; i++)
        {
            if(c[i]!=0)
            {
                num1++;
            }
        }
        
         for(i=2; i<=b; i++)//对数组进行初始化
        {
            c[i] = i;
        }        
        for(i=2; i<=sqrt(b); i++)//进行筛选
        {
            
            for(j=i+1; j<=b; j++)
            {
                if(c[i]!=0 && c[j]!=0 && c[j]%c[i]==0)
                {
                    c[j]=0;
                }
            }
        }

        for(i=2; i<=b; i++)
        {
            if(c[i]!=0)
            {
                num2++;
            }
        }
        if(num1>num2)
        {
           t=num1;
           num1=num2;
           num2=t;   
        }
        printf("%d\n",num2-num1+1);
    }
    return 0;
}


第二种求法：
#include <stdio.h>
#define  N 1000001
int prime[N];
int main()
{
        int K,i,c;
        scanf("%d",&K);
            for(i=2;i<N;i++)  //筛法求素数
        {
            prime[i]=1;   
        }
        prime[0]=prime[1]=0;
        for(i=2;i<=1000;i++)
        {
            if(prime[i])
            {
                for(c=i*i;c<=N;c+=i)
                {
                    prime[c]=0;   
                }
            }
        }
        while(K--)
        {
            int t,a,b,num=0;
            scanf("%d %d",&a,&b); //输入a b的值，如果a>b则将a与b的值交换
            if(a>b)
            {
                t=a;
                a=b;
                b=t;
            }
               
   
        
        for(i=a;i<=b;i++) //ab之间有多少个素数
        {
            if(prime[i]==1)
            {
                num++;
            }   
        }
        printf("%d\n",num);
    }
    return 0;            
}


测试没问题了，不过我在网站提交还是显示time limit exceed 没有ac还是要继续改

收到的鲜花

• 九转星河 于 2016-10-31 12:51 送鲜花  5朵   附言：我很赞同

第二种思路做法很优，筛数法和我接触传统的穷举法不同，可以大大减少运算量。我自己也尝试做了一个，但我用的穷举法运算量很大，没有你的筛数法优。
我的程序代码如下

#include<stdio.h>
#include<math.h>
int main()
{
    int num,k;
    scanf("%d",&k);//案例个数
    while (k--)
    {
        int i,j,t,a,b;
        scanf("%d%d",&a,&b);//ab为所求区间
        if (a>b)
        {
            t=a;
            a=b;
            b=t;
        }
        for (num=0,i=a;i<b;i++)
        {
            for (t=1,j=2;j<=sqrt(i);j++)
                if (i%j==0)t=0;
            if (t==1&&i!=1)
                num++;
        }
        printf("%d\n",num);
    }
    return 0;/*该方法没有用数组处理，用穷举法，没有标记该数是否是素数，省空间，但运算量大
             适用于的取值范围较小的区间*/
}

我没有用数组处理，直接把素数的值累加。这样可以节省4000004个字节（相当于3MB）的空间，但如果输入区间范围很大，则运算量很大很大，甚至超出了编译器的允许运算范围（我用vc版测试的，我的穷举法不能从1算到1000001)，但是当计算区间范围较小的便有空间优势。你可以比较一下两种做法，它们的适用范围不同，但如果不受空间限制，还是题主的做法较优。