2.素数和复合数

首先素数和复合数是所有大于一的正整数。 我们对于素数的定义就是该数只能被一和它本身整除，不能被其他数整除。例如2只能被1和2整除，3只能被，1和3整除，5只能被1和5整除等等。而复合数则是指除了能被一和它本身整除之外，还能被其他的数整除的数。例如4除了能被1和4整除外，还能被二整除，6除了能被1和6整除外，还能被2和3整除等等。

如果一个正数a有一个因数b，而b又是素数，则b就叫做a的素因数。我们任意举两个例子。例如12=3×4，所以3和4都是12的因数，又因为3是素数，而4不是素数，所以三是12的素因数，而4不是12的素因数。比如15=3×5，3和5都是素数，所以3和5都是15的素因数。再比如16=4×4，又因为4是一个复合数，所以4不是16的素因数。那么16就不存在素因数了吗？不，16=2×8，我们可以很明显的看出2是一个素数，而8是一个复合数，所以2是16的素因数。所以在考虑一个数是否存在素因数时，我们首先要考虑该数是素数还是复合数，如果是复合数，那么它的因数中是不是存在素数。

那么所有数都存在素因数吗？我们举如下一个例子。如果a是一个素数，则a的大于一的因数，只有一个就是a，所以a>1的最小因数就是素数a。那么我们可以很轻松的看出来，a的素因数就是a。如果a是复合数，那么除了a与1外，还存在着至少一个因数。假设除了a与1外最小的那一个因数是一个复合数，那么这个数一定存在一个大于一并且不等于它本身的一个因数。我们假设该数为X，它的因数为Y。那么Y能整除X，X能整除a。根据上一篇文章中的一条引理，我们可以知道。 Y一定是a的因数。（设a，b，c都是整数 ，a|b，b|c。因为a|b，所以由定义可知有一个整数d它使得b=ad，又由于b|c所以有一个整数e，它使得c=be，由c=be和b=ad有c=ade，由于e和d都是整数，所以de也是整数，由定义可知c=ade有a|c。所以当a，b，c都是整数，a|b，b|c时有a|c。） Y一定小于X，但根据上述陈述 X为除a与Y最小的因数。所以该假设不成立。那么则得知X一定是一个素数。即证明任何大于1的整数都至少有一个素因数。

那么观察一个正整数a是不是素数是否一定要列出其所有的因数来进行判断呢？其实不用，这里有一个更简单的方法。设a是一个大于一的整数。设a=bc ，b和c均是大于1的整数。若b>√a，c>√a则bc>√a √a=a，这与a=bc不符。所以该假设不成立，所以a≠bc，若此时≤√a的素数都除不尽，则a是素数。