1.2.2　素数与合数

一个数，如果只有1和它本身两个约数，则称为素数（或称质数）.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.

一个数，如果除了1和它本身还有别的约数，则称为合数.例如，4，6，8，9，12都是合数.

0和1不是素数也不是合数.自然数除了0和1外，不是素数就是合数.如果把自然数按其约数的个数的不同分类，可分为素数、合数、0和1.

如何找出某个正整数n内的所有素数呢？公元前250年由古希腊数学家埃拉托斯特提出了一种筛法，现在称之为埃拉托斯特筛法，简称埃氏筛或爱氏筛，是一种简单地找出某个正整数n内的所有素数的方法.其方法如下：

首先，列出从2到n的所有整数.先用2去筛，即把2留下，把2的倍数剔除掉；再用留下来的比2大的最小数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用留下来的比3大的最小数5筛，不断重复下去，直到这个数大于.留下来的就全部是素数.

例如，求25以内的素数的步骤如下：

（1）列出2以后的所有整数：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

（2）标出序列中的第一个素数，也就是2（序列中第1个），划掉2的倍数（用下画线标出），序列变成

（3）25>2×2，继续标出序列中的第二个素数，也就是3，划掉3的倍数（用下画线标出），即9，15，21，序列变成

（4）25>3×3，继续标出序列中的第三个素数，也就是5，划掉5的倍数（用下画线标出），即25，序列变成

（5）现在这个序列中最大数23<5×5，那么剩下的序列中所有的数都是素数，即

2 3 5 7 11 13 17 19 23