Eratosthenes筛子是一种用于找出一定范围内所有素数的算法。它的第二个循环从当前素数的平方开始,是因为这样可以避免重复标记非素数。
具体来说,Eratosthenes筛子的算法步骤如下:
为了理解为什么第二个循环从当前素数的平方开始,我们可以考虑一个例子。假设我们要找出范围为1到100的所有素数。
首先,我们从2开始,将2的倍数(除2以外)标记为非素数。然后,我们找到下一个未被标记的数字3,将3的倍数(除3以外)标记为非素数。接着,我们找到下一个未被标记的数字5,将5的倍数(除5以外)标记为非素数。依此类推,我们找到下一个未被标记的数字7,将7的倍数(除7以外)标记为非素数。
现在,我们来考虑为什么第二个循环从当前素数的平方开始。假设当前素数为p,如果我们从p的下一个数开始标记倍数,即从p+1开始,那么在之前的循环中,已经有其他素数的倍数被标记为非素数了。这些已经被标记的倍数中,一定存在一个小于p的素数q,且q的倍数也被标记为非素数。那么在当前循环中,当我们到达q时,它的倍数已经被标记过了,因此从q的下一个数开始标记是多余的。
因此,为了避免重复标记,第二个循环从当前素数的平方开始,即从p^2开始。这样可以确保在当前循环中,所有小于p的素数的倍数都已经被标记过了,避免了重复工作,提高了算法的效率。
腾讯云相关产品和产品介绍链接地址:
领取专属 10元无门槛券
手把手带您无忧上云