我是C初学者;)
下面的代码有多好,可以找到2-1000之间的所有素数：
下面的代码有多好,可以找到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";
}
}
解决方法
当j = i时你停止.
第一个简单的优化是在j = sqrt(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的最小因子. 这是一些难以理解的代码！
