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

Question

素数知多少？
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;
}

Answer 1

我建议使用这种

#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