c - 优化此代码，使其代码运行时间小于 1s

Question

我写了这个c程序。这运作良好。我想要非常大的值，例如 1000000。这应该在不到 1 秒的时间内运行。

该程序生成 n>1 的序列。 a[0]=a[1]=0 且 a[n]=a[n-1]+f(n)，其中 f(n) 是 n 的最小素因数。

#include<stdio.h>
int fn(long no)
{
    long i;
    for (i = 2; i <= no; i++)
    {
        if (no % i==0)
        {
            return i;
            break;
        }
    }
}

int main(void)
{
    int t,i;
    long n,a1,j;
    scanf("%d",&t);

    for(i=0;i<t;i++)
    {
        a1=0;
        scanf("%ld",&n);
        for(j=2;j<=n;j++)
        {
            a1 = a1 + fn(j);

        }
     printf("%d\n",a1);
    }
}

Answer 1

只需进行如下修改，您就会看到很大的差异:

#include<math.h>

int fn(long no)
{
    long i;
    int sqrtno= (int)sqrt((double)no);
    for (i = 2; i <= sqrtno; i++)
    {
        if (no % i==0)
        {
            return i;
        }
    }

    return no;
}

当达到no的平方根时，无需继续寻找除数，因为当一个除数大于此时，另一个就较小。