首页 > 代码库 > 求质数的方法解析

求质数的方法解析

质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。换句话说,只有两个正因数(1和自己)的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。合数是由若干个质数相乘而得到的。所以,质数是合数的基础,没有质数就没有合数。

求素数的方法有很多种,最简单的方法是根据素数的定义来求。对于一个自然数N,用大于1小于N的各个自然数都去除一下N,如果都除不尽,则N为素数,否则N为合数。
但是,如果用素数定义的方法来编制计算机程序,它的效率一定是非常低的,其中有许多地方都值得改进。
第一,对于一个自然数N,只要能被一个非1非自身的数整除,它就肯定不是素数,所以不
必再用其他的数去除。
第二,对于N来说,只需用小于N的素数去除就可以了。例如,如果N能被15整除,实际
上就能被3和5整除,如果N不能被3和5整除,那么N也决不会被15整除。
第三,对于N来说,不必用从2到N一1的所有素数去除,只需用小于等于√N(根号N)的所有素数去除就可以了。这一点可以用反证法来证明:
如果N是合数,则一定存在大于1小于N的整数d1和d2,使得N=d1×d2。
如果d1和d2均大于√N,则有:N=d1×d2>√N×√N=N。
而这是不可能的,所以,d1和d2中必有一个小于或等于√N。