怎么辨别质数
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/08 01:31:38
怎么辨别质数
怎么辨别质数
怎么辨别质数
质数（prime number）又称素数,有无限个.一个大于1的自然数,除了1和它本身外,不能被其他自然数整除（除0以外）的数称之为素数（质数）；否则称为合数.根据算术基本定理,每一个比1大的整数,要么本身是一个质数,要么可以写成一系列质数的乘积；而且如果不考虑这些质数在乘积中的顺序,那么写出来的形式是唯一的.
只有1和它本身两个因数的自然数,叫质数（或称素数）.（如：由2÷1=2,2÷2=1,可知2的因数只有1和它本身2这两个约数,所以2就是质数.与之相对立的是合数：“除了1和它本身两个因数外,还有其它因数的数,叫合数.”如：4÷1=4,4÷2=2,4÷4=1,很显然,4的因数除了1和它本身4这两个因数以外,还有因数2,所以4是合数.）
100以内的质数有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97,在100内共有25个质数
质数的个数是无穷的.欧几里得的《几何原本》中有一个经典的证明.它使用了证明常用的方法：反证法.具体证明如下：假设质数只有有限的n个,从小到大依次排列为p1,p2,……,pn,设N=p1×p2×……×pn,那么,N+1是素数或者不是素数.
如果N+1为素数,则N+1要大于p1,p2,……,pn,所以它不在那些假设的素数集合中.
如果N+1为合数,因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1,所以N+1不可能被p1,p2,……,pn整除,所以该合数分解得到的素因数肯定不在假设的素数集合中.
因此无论该数是素数还是合数,都意味着在假设的有限个素数之外还存在着其他素数.所以原先的假设不成立.也就是说,素数有无穷多个.