2

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

我正在运行一个从 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;
}
4

4 回答 4

5

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

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

这大约是 n*n/4 = O(n^2)。您的循环行程次数太高了。

于 2013-04-21T16:36:04.410 回答
2

这取决于系统和编译器。在 Linux 上，使用 GCC 4.7.2 并使用gcc -O2 vishaid.c -o vishaid程序编译立即返回，并且编译器通过删除它们来优化所有调用isPrime1（我检查了生成的汇编代码gcc -O2 -S -fverbose-asm，然后main甚至不调用isPrime1）。GCC 是对的：因为isPrime1没有副作用并且没有使用它的结果，所以可以删除它的调用。那么for循环体是空的，所以也可以优化。

要吸取的教训是，在对优化的二进制文件进行基准测试时，最好在代码中产生一些真正的副作用。

此外，算术告诉我们，i如果没有小于其平方根的除数，则某些是素数。所以更好的代码：

int isPrime1(long t) {
  long i;
  double r = sqrt((double)t);
  long m = (long)r;
  if(t==1) return 0;
  if(t%2==0) return 0;
  for(i=3;i <= m;i +=2)
    if(t%i==0) return 0;
  return 1; 
}

在我的系统上（带有 i7 3770K Intel 处理器的 x86-64/Debian/Sid，运行该程序的核心频率为 3.5GHz）long-s 是 64 位。所以我编码

int main ()
{
  long i = 0;
  long cnt = 0;
  time_t s, e;

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

大约 4 分钟后，它仍然打印了很多行，包括

#6819840: 119566439
#6823936: 119642749
#6828032: 119719177
#6832128: 119795597

我猜这需要几个小时才能完成。30 分钟后它仍在吐痰（缓慢）

#25698304: 486778811
#25702400: 486862511
#25706496: 486944147
#25710592: 487026971

实际上，该程序需要4小时16分钟才能完成。最后的输出是

#105086976: 2147139749
#105091072: 2147227463
#105095168: 2147315671
#105099264: 2147402489

   Time : 15387 secs

顺便说一句，这个程序仍然效率很低：包中的程序primes响应速度更快/usr/games/primesbsdgames

% time /usr/games/primes 1 2147483647 | tail
2147483423
2147483477
2147483489
2147483497
2147483543
2147483549
2147483563
2147483579
2147483587
2147483629
/usr/games/primes 1 2147483647 
     10.96s user 0.26s system 99% cpu 11.257 total

它仍然打印了 105097564 行（大多数被 跳过tail）

如果您对质数生成感兴趣，请阅读几本数学书籍（如果您对效率感兴趣，它仍然是一个研究主题；您仍然可以获得该主题的博士学位。）。从 Wikipedia 上的 Erastothenes和素性测试页面的筛子开始。

最重要的是，首先用调试信息和所有警告编译您的程序（即gcc -Wall -g在 Linux 上）并学习使用您的调试器（即gdb在 Linux 上）。然后，您可以在大约一两分钟后中断您调试的程序（使用Ctrl-Cunder gdb，然后让它继续使用cont命令 to gdb），然后观察imain 中的计数器正在缓慢增加。也许还要求提供分析信息（然后使用-pg选项）。在编写复杂的算术代码时，阅读有关它们的优秀数学书籍是非常值得的（素数测试是一个非常复杂的主题，是大多数密码算法的核心）。gccgprof

于 2013-04-21T16:36:55.923 回答
1

这是测试素数的一种非常低效的方法，这就是它似乎挂起的原因。在网上搜索更有效的算法，例如埃拉托色尼筛法

于 2013-04-21T16:39:09.263 回答
0

这里试试这个，看看是不是真的死循环

int main()
{
    long i=0;
    time_t s,e;

    s = time(NULL);
    for(i=3; i<2147483647; i++)
    {
        isPrime1(i);

        //calculate the time execution for each loop
        e = time(NULL);
        printf("\n\t Time for loop %d: %ld secs", i, e - s );
    }

    return 0;
}
于 2013-04-21T16:36:24.377 回答