第十三讲质数与合数（2）

如歌的行板 2007-02-08

展开全文

第十三讲质数与合数（2）

　　我们已学习过合数和质数的一些简单知识，对它们有了初步的了解。

　　我们可以按每个整数的约数个数的不同，将自然数分为三类：

　　第一类：只有一个约数，是“1”。

　　第二类：只有两个约数的，即1和本身的，是质数。

　　第三类：除1和本身还有其它的约数，是合数。

　　从以上的分类方式中，能够清楚地看出两点，①“1”这个数既不是质数，也不是合数。②“质数与合数放在一起并不是全部自然数”。这两点十分重要，运用中容易出现问题。

　　如何判断一个大于1的自然数是质数还是合数呢，下面介绍几种常见的方法。

例1 377是质数吗？

解：我们用从小到大的一个个质数，逐个试除377，看看有没有能整除377的，即用2，3，5，7，11，13，…去试除。发现13|377而13是1和377以外的约数，所以377不是质数。

　　两千多年前，埃及亚历山大图书馆的管理员埃托色尼就是用这种方法选出质数的：在全体自然数里，先把1去掉，然后再把2的倍数去掉（保留2），再把3的倍数去掉（保留3），……，依次地做下去，最后剩下的就都是质数了。这种方法叫“筛选法”。

例2 有一个2n+1位整数（n是整数，n≥1）

解法1：我们观察这个数的数字特征，可以看出，它的各个数位数字和是3的倍数。

　　由于n+1是整数，得3|（n+1）×3，所以3是原数的约数，显然3是

　　由上面的解法中，可以看到“整除”知识在判断质数与合数时有很大用处，要想迅速找出一个整数的约数，就要对数的整除特征非常熟练，这对提高筛选的速度大有好处。

解法2：还可以把这个数分解一下，把这个数中间的“3”拆开。

　　把这个数字拆开的主要目的是能提出公因数做因数分解。这种方法不但能说明一个数是合数，还提供了分解因数的一种方法。

　　对于质数来讲，由于它至今没有统一的数学式子来表示，人们对它的了解仍是很不全面的。已经知道：质数有无限多个（这在初中可以证明），并且一般来说，随着数值越大就越来越稀少。有人统计过五千以内的质数分布情况：

　　1～1000中有168个质数，

　　1001～2000中有135个质数，

　　2001～3000中有127个质数，

　　3001～4000中有120个质数，

　　4001～5000中有119个质数。

例3 在三张纸片上分别写上三个最小的连续的奇质数，如果随意从其中取出至少一张组成一个数，其中有几个是质数？将它们写出来。

解：三个最小的连续奇质数是指3，5，7。“至少取出一张”的含义是：取一张组成一位数，取两张组成两位数，取三张组成三位数。

　　我们下面分三种情况讨论一下：

　　（1）如果取出了三张：这三个数字的和3+5+7=15是3的倍数，所以任意取出的三位数都不是质数。

　　（2）如果取出了两张：所有可能的两位数有35，37，53，57，73，75六种，其中质数是37，53，73。

　　（3）只取出一张时：3、5、7均为质数。

　　合乎要求的质数是3、5、7、37、53、73。

例4 5112的约数有多少个。

分析：首先把5112分解为质因数的乘积，进而求出全部约数。

解：5112=2×2×2×3×3×71=2³×3²×711

　　5112的约数都是由2，3，71这些因子构成，约数中，关于2的因子有四种情况：含有三个2、含有两个2、含有一个2和不含有2；关于3的因子有三种情况：含有两个3、含有一个3和不含3；关于71的因子有两种情况：含有一个71和不含有71。

　　根据乘法原理，含有2、3、71的约数的种类有4×3×2=24种，即有24个约数。

　　用我们前面提过的约数个数的公式，也可以很简捷的求出：（3+1）×（2+1）×（1+1）=24

例5 在1～300之间，求出：约数个数正好是15个的自然数。

解：首先看一下组成这数的质因子的情况是什么样子的。

　　15=1×15=3×5

　　根据约数的个数的公式，这个自然数中只含有两个不同的质因数，不妨设这两个质因数分别是A、B。

　　（1）当15分解为1×15=（0+1）×（14+1），说明这个自然数可以写为A0×B14=B14，即是14个相同质数的乘积，考虑到自然数的范围在1～300之间，设B=2，但是214=16384＞300，超出范围，因此这种情况是不可能的。

　　（2）当15分解为3×5=（2+1）（4+1）时，即自然数可记为A2×B4

　　<1>当A=2，B=3时，2²×3⁴=324＞300（超出）

　　<2>当A=3，B=2时，3²×2⁴=144＜300（满足条件）

　　<3>当A=5，B=2时，5²×2⁴=400＞300（超出）

　　由此可以得出，对于任何A＞3或B＞2的取法都不符合条件。

　　所以，在1～300之间，约数个数是15个的自然数只有144。

例6 有一个自然数含有10个不同的约数，但质约数只有2和3。那么，这个自然数最大是几？

解：设这个自然数表示为2^m×3ⁿ（m，n是整数）

　　根据约数个数公式：

　　约数个数10=（m+1）×（n+1）=1×10=2×5

　　这样，m，n，的取值只有四种可能：

　　即这个自然数有四种可能的形式：

　　2⁰×3⁹=3⁹，2⁹×3⁰=2⁹，2¹×3⁴，2⁴×3¹

　　其中前面两个不合条件应去掉。

　　比较2¹×3⁴和2⁴×3¹，显然最大的是2¹×3⁴=162。

例7 房间里有100盏电灯，并且编号号码1，2，3，…，100。每盏灯上有一个拉线开关开始时电灯全都是关的。100位同学由房间外逐个走进去。第一位同学，把编号是1的倍数的灯的开关拉动一下；第二位同学，把编号是2的倍数的灯的开关拉动一下；第三位同学，把编号是3的倍数的灯的开关拉动一下，……，第100位同学，把编号是100的倍数的灯的开关拉动一下。这时，房间里有哪些号码的灯是亮的？

分析：根据这个约定，第一个同学应当拉动1，2，3，……100，各个编号的灯，第二个同学应当拉动2，4，6，8，……100，各个编号的灯，第三位同学应当拉动3，6，9，……，99各个编号的灯，第100位同学只拉动100号灯。

　　由于开始时灯是关着的，被拉动偶数次的灯还是不亮，而被拉动奇数次的灯才会亮。灯的编号有多少个约数，它就被该约数号码的所有同学拉动有多少次。看来1～100中每个整数约数的个数是奇数还是偶数，决定了最后的结果。我们可以分析几个数的约数个数，看其奇偶性的规律。