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

Question

下面的函数检查整数是否为素数.

我正在运行一个for循环,从3到2147483647(长int的+ ve限制).

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

#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).你的环路旅行次数太高了.