c - 为什么这段代码会进入无限循环

Question

下面这个函数检查一个整数是否为素数。

我正在运行从 3 到 2147483647 的 for 循环(+ve 限制 long int)。

但是这段代码挂了，找不到原因？

#include<time.h>
#include<stdio.h>
int isPrime1(long t)
{
    long i;
    if(t==1) return 0;
    if(t%2==0) return 0;
    for(i=3;i<t/2;i+=2)
    {
        if(t%i==0) return 0;
    }
    return 1;
}
int main()
{
    long i=0;
    time_t s,e;

    s = time(NULL);
    for(i=3; i<2147483647; i++)
    {
        isPrime1(i);
    }
    e = time(NULL);
    printf("\n\t Time : %ld secs", e - s );
    return 0;
}

Answer 1

它最终会终止，但需要一段时间，如果你在内联你的 isPrime1 函数时查看你的循环，你有类似的东西:

for(i=3; i<2147483647; i++)
   for(j=3;j<i/2;j+=2)

大致为 n*n/4 = O(n^2)。您的循环次数太高了。