素数的定义：恰有两个不同正整数因子的整数成为素数。

大于1的每个正整数都至少能被两个整数整除，因为正整数可以被1和他自己整除。

合数的定义：大于1，又不是素数的正整数。

 

算术基本定理：每个大于1的正整数都可以唯一地写为两个或多个素数的乘积，其中素数因子以非递减序出现。

根据此定理可以看出，素数是构成正整数的积木。

 

定理2：如果n是个合数，那么n必有小于或等于√n的一个素因子。

 

定理3：有无限多个素数。

 

整数的素因子分解算法分析：

　　给定一个整数n，可以从最小的素数2开始，从小到大用一个一个素数去除n。如果n有素数因子，那么必定能够找到一个不大于√n的素因子p，否则，根据定理2，n即为素数。如果找到了素因子p，那么可以对n/p继续进行素数除法。这里应该从p开始，因为如果n没有小于p的素因子，那么n/p就不可能有小于p的素因子。这样，如果找到了素因子q，那么继续对n/(pq)做素数除法，直到最后分解的结果为一个素数。

举例说明：对7007进行素因子分解。

　　从2开始，依次用2，3，5，7...等素数除7007，发现2，3，5除不尽，但7可以，7007/7=1001， 然后从7开始除1001，可以除尽，1001/7=143，从7开始除143，发现7除不尽，然后是11，143/11=13，能够整除，而得到的13为素数，分解过程结束。于是，整理上述过程可得，7007的素因子分解结果为7²*11*13.