由于大于1的正整数不是质数就是合数，所以判定质数与判定合数等价，下面我们介绍质数的判定.
早在两千多年以前，古希腊的埃拉托斯特尼（Eratosthenes)就设计了一种把质数从正整数中筛选出来的方法，俗称筛法，至今人们仍然采用这个重要方法.
比如，要把100以内的质数筛选出来，可用如下过程：
先把2至100的正整数全部按大小次序排列出来；把2后面所有2的倍数划去，照“2”依次处理“3”“5”“7”；最后剩下的数整理出来就是100以内的质数：
划去7的倍数以后，就得到了100以内的全部25个质数，这是为什么呢？为了回答这个问题，先证明如下结论.
定理1 设a是大于1的正整数，若p是a的大于1的最小正因数，则p必为质数.
证明 若p不为质数，因为p＞1，所以p为合数，所以p存在1和p以外的正因数q，使得q∣p.
因为p∣a，所以q∣a，所以q是a的1和a以外且小于p的正因数，这与已知矛盾，故p必为质数.
定义2 若p既是质数又是正整数a的因数，则p叫作a的质因数.
定理1表明，任意大于1的正整数都至少有一个质因数.
下面我们来说明筛法的理论根据.
由例2可见，判定一个数是质数还是合数是一件麻烦的事情.尽管如此，千百年来人们判定、寻找最大质数的工作始终没有停止!感兴趣的读者请阅读本书第二章“拓展阅读”.(www.xing528.com)
不难想象，质数有无限多.这一结果早在两千多年以前欧几里得（Euclid)就给出了漂亮的证明.
定理3 质数有无限多个.
证明 设正整数集内仅有n个质数p1，p2，p3，…，pn.作
显然，m是p1，p2，p3，…，pn以外的大于1的正整数，由定理1知，m有质因数p且p≠p1，p2，p3，…，pn（否则，p|p1p2p3…pn，而p|m，故p|（m-p1p2p3…pn=1)，这与p为质数大于1矛盾)，故p为p1，p2，p3，…，pn以外的质数，这与反证假设矛盾.
故质数有无限多个.
尽管质数有无限多个，但其分布大致上是越来越少，甚至我们可以找到连续的n个合数.
例3 求证：对任意大于1的整数n，存在连续的n个合数.
证明 记1×2×3×…×n=n!（读作n的阶乘).
考虑n个连续整数：
它们依次分别可被2，3，…，（n＋1)整除，故它们是连续的n个合数.
如n=3，由（3＋1)!=4!=24可找到3个连续合数26，27，28.
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
