救命啊，程序超时了，可是想不出别的方法了

问题描述：

素数知多少？
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 1232 Accepted: 330
Description

在给定区间[1,n]中有多少个素数？

Input

每行一个整数n(1<=n<=1000000)

Output

[1,n]之间素数的个数，独立一行

Sample Input

1013
100
Sample Output

170
25


#include<stdio.h>
int arr[1000000] = { 0 };
int main()
{
    
    int n;
    while (scanf("%d", &n))
    {
        for (int i = 2; i <= n; i++)
        {
            if (arr[i]==0)
            {
                for (int j = i+i; j <= n; j+=i)
                {
                    arr[j] = 1;
                }
            }
        }
        int cot = 0;
        for (int i = 2; i <= n; i++)
        {
            if (arr[i] == 0)
            {
                cot++;
            }
        }
        printf("%d\n", cot);
    }    
    return 0;
}

答

我建议使用这种

#include<stdio.h>
#include<math.h>
inline bool check(int x){
    if(x<2)return false;
    int end=sqrt(x);
    for(int i=2;i<=end;++i)if(x%i==0)return false;
    return true;
}
int n,ans=0;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)if(check(i))++ans;
    printf("%d",ans);
}

一个数n一定可以被分解为两个实数的乘积。所以实际上只需要检查根号n以内的数是不是它的因数就可以了。
因为若一个大于根号n的数是n的因数的话，那么那个数一定要和一个小于根号n的数相乘得到n，所以证明完毕，OK

答

这么改下，试试：

#include <stdio.h>
int  main()
{
    int i ,j ,IsPrime ,n ,cnt;
    while(1)
    {
         scanf("%d",&n);
         if(n == -1) break;    //-1 结束输入
         for (i = 2,cnt = 0; i <= n; i++)
         {
              for (j = 2,IsPrime = 1;IsPrime && (j*j <= i); j++)
                   if (i % j == 0) IsPrime = 0;
              if (IsPrime)  cnt++;
         }
         printf("%d\n", cnt);
    }
    return 0;
}

救命啊，程序超时了，可是想不出别的方法了

相关推荐