如何证明埃拉托斯特尼筛法!检查一个正整数N是否为素数,最简单的方法就是试除法,将该数N用小于等于根号N的所有素数去试除,若均无法整除,则N为素数

来源:学生作业帮助网 编辑:作业帮 时间:2024/04/28 03:29:24
如何证明埃拉托斯特尼筛法!检查一个正整数N是否为素数,最简单的方法就是试除法,将该数N用小于等于根号N的所有素数去试除,若均无法整除,则N为素数

如何证明埃拉托斯特尼筛法!检查一个正整数N是否为素数,最简单的方法就是试除法,将该数N用小于等于根号N的所有素数去试除,若均无法整除,则N为素数
如何证明埃拉托斯特尼筛法!
检查一个正整数N是否为素数,最简单的方法就是试除法,将该数N用小于等于根号N的所有素数去试除,若均无法整除,则N为素数

如何证明埃拉托斯特尼筛法!检查一个正整数N是否为素数,最简单的方法就是试除法,将该数N用小于等于根号N的所有素数去试除,若均无法整除,则N为素数
利用反证法:假设这样筛出来的N是合数,且不能被小于等于其平方根的所有素数整除,那么N一定能被大于其平方根小于其本身的某个素数整除.记该素数为M,则√N