我能让这个 C 程序更快吗？

Question

我需要编写一个程序来打印所有素数，这是我所做的:

#include <stdio.h>

int main(void) {
    long long t,m,n,i,i2,i3,found;
    float p;
    scanf ("%lld" , &t);
    for (i=1;i<=t;i++) {
        scanf ("%lld%lld" , &m ,&n);
        for (i2=m;i2<=n;i2++) {
            found=0;
            for (i3=2;i3<=i2/2;i3++) {
                p=(float)i2/i3;
                p=p-i2/i3;
                if (p==0) {
                    found=1; 
                }
            }
            if ((found==0) && (i2!=1)) {
                printf ("%lld\n" , i2); 
            }
        }
        printf ("\n");
    }
    return 0;
}

我的时间限制是6秒，用这个代码是不可能的，而且m和n之间的差异最大是100000，并且1<=n<=m<=1000000000

Answer 1

有复杂的数学算法，例如 Sieve of Atkin ，可以非常快速地找到素数，但出于您的目的，请考虑:

如果分解得足够远，每个非素数都可以被素数分解。

如果您已经达到 sqrt(n) 但仍未发现它可以分解，那么它就无法分解，因为任何大于 sqrt(n) 的数字都必须与小于 sqrt 的数字一起分解(n) 达到您正在寻找的数字。

因此，测试从 2 到 sqrt(n) 的每个素数，看看您的 n 是否是素数。如果 2 和 sqrt(n) 之间的素数都不是 n 的因数，则 n 一定是素数。

这应该满足您的作业的速度要求。