书中的C Prime编号任务

发布时间：2020-12-16 03:41:25 所属栏目：百科来源：网络整理

导读：我是C初学者;) 下面的代码有多好,可以找到2-1000之间的所有素数： int i,j;for (i=2; i1000; i++) { for (j=2; j=(i/j); j++) { if (! (i%j)) break; if (j (i/j)) cout i " is primen"; }} 解决方法当j = i时你停止. 第一个简单的优化是在j = sqrt(i)时停

我是C初学者;)
下面的代码有多好,可以找到2-1000之间的所有素数：

int i,j;

for (i=2; i<1000; i++) {
  for (j=2; j<=(i/j); j++) {
    if (! (i%j))
      break;
    if (j > (i/j))
      cout << i << " is primen";
  }
}

解决方法

当j = i时你停止.
第一个简单的优化是在j = sqrt(i)时停止(因为不存在大于其平方根的数字因子).

更快的实现是例如sieve of eratosthenes.

编辑：代码看起来有点神秘,所以这是它的工作原理：

内部for的终止条件是i / j,相当于j< i(更清楚),因为当最终有j == i时,我们将有i / j == 0并且for将会中断. 下一次检查是否(j>(i / j))真的很讨厌.基本上它只是检查循环是否达到for的结束条件(因此我们有一个素数)或者如果我们达到显式中断(没有素数).如果我们达到了结尾,那么j == i 1(考虑一下)=> i / j == 0 =>这是一个素数.如果我们中断,这意味着j是i的因子,但不仅仅是任何因子,实际上是最小的(因为我们在第一个j处除以i)！由于j是最小因子,因此另一个因子(或剩余因子的乘积,由i / j给出)将大于或等于j,因此测试.如果j <= i / j,我们中断,j是i的最小因子. 这是一些难以理解的代码！

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!