摘要: 思想:对于不超过n的每个非负整数P,删除2*P, 3*P…,当处理
完所有数之后,还没有被删除的就是素数。
若用vis[i]==1表示已被删除,则代码如下:
先分析代码一:
这个代码就是简单的将Eratosthenes筛选法描述出来。不用多说。
分析代码二:
考虑几点:
1.为何从i=2~m?
因为下面的j是从i*i开始的。
2.为何j从i*i开始?
因为首先在i=2时,偶数都已经被删除了。
其次,“对于不超过n的每个非负整数P”, P可以限定为素数,
为什么?
因为,在 i 执行到P时,P之前所有的数的倍数都已经被删除,若P
没有被删除,则P一定是素数。
而P的倍数中,只需看:
(p-4)*p, (p-2)*p, p*p, p*(p+2), p*(p+4)
(因为P为素数,所以为奇数,而偶数已被删除,不需要考虑p*(p
-1)等)(Tanky Woo的程序人生)
又因为(p-4)*p 已在 (p
阅读全文