书中的C++ Prime数字任务

Question

我是一个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 prime\n";
  }
}

Answer 1

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

更快的实施方案是例如eratosthenes的筛子.

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

内部for的终止条件i/j相当于j<i(更清楚),因为当最终有时j==i,我们将拥有i/j==0并且for将会中断.

接下来的检查if(j>(i/j))非常讨厌.基本上它只是检查循环是否达到for的结束条件(因此我们有一个素数)或者如果我们达到显式中断(没有素数).如果我们击中了for的结尾,那么j==i+1(考虑一下)=> i/j==0=>这是一个素数.如果我们中断,它意味着j是一个因素i,但不仅仅是任何因素,实际上是最小的(因为我们在第一个j分开时退出i)!由于j是最小的因素,另一个因素(或剩余因子的乘积,由下式给出i/j)将大于或等于j,因此测试.如果j<=i/j,我们打破了,j是最小的因素i.

这是一些难以理解的代码!

Answer 2

对于我们在这里发布的一大堆文字，一个简单的答案是：审判庭！如果有人提到这个任务所基于的数学基础，我们会节省大量时间;)