小学数学知识问答300例—怎样判断质数

173.如何判断一个数是否是质数？

正确而快速地判断一个自然数是否是质数是数的可除性的一项重要基本技能。

由于大于2的质数必须是奇数(奇数不一定是质数)，当判断一个自然数是否是质数时，首先要看它是奇数还是偶数。如果是大于2的偶数，这个数肯定不是质数，而是一个复合数。如果它是奇数，它可能是质数。在这种情况下，通常使用以下两种方法:

(1)查表法:

主要是指检查“质数表”。质数表的编制过程如下:根据自然序列，第一个数1不是质数，所以必须排除。那么从2到500的所有自然数都是按顺序写的。在这些数字中，2是一个质数，把它放在后面，把2的所有倍数都划在2之后，2之后的3是质数，然后把3之后的3的所有倍数都划在3之后，依此类推，剩下的都是500以内的质数。

第一个使用上述方法寻找素数的人是古希腊数学家厄拉多塞。因为他在蜡板上写自然数，并在开始时把不是质数的数字(复数)分别打孔，所以在蜡板上打了许多像筛子一样的孔。后来，每个人都把这种求素数的方法称为“筛法”。

以下是通过筛选方法找到的500以内的质数表:

这种质数表也可以编译成更大的数字范围，如1000以内的质数表等。为了判断一个自然数是否是质数，如果它在表中指定的数值范围内，可以用查表法来判断。

(2)审判庭:

如果手头没有质数表，我们可以用试除法来判断自然数是否是质数。例如，为了判断143，179是否是质数，我们可以试着用2，3，5，7，11等质数来除它们。从小到大。一般来说，在20以内去掉8个质数2、3、5、7、11、13、17和19就足够了。例如，143，这个数字的位数是3，排除了被2和5整除的可能性。它的位数之和是1+4+3=8，不可能被3整除。口头计算也证明了它不能被7整除。除以11，商正好是13，因此143不是质数。

179的测试和移除过程如下:

179÷2 = 59…2

179÷3 = 66…1

179÷5 = 35…4

179÷7 = 25…4

179÷11 = 16…3

179÷13 = 13…10

179÷17 = 10…9

当179÷17得到的不完全商10比除数大17小时时，就没有必要再继续尝试，179被确定为质数。这是因为2，3，5，7，11，13和17不是179的质因数。因此，179不再具有大于17的质因数，或者179不能被小于10的数整除。因此，179必须是质数。

综上所述，当用试除法判断一个自然数A是否是素数时，只要用每个素数从小到大依次去掉A，如果一个素数是可整除的，这个A就可以确定不是素数；如果它不能被整除，如果不完全商小于这个质数，那么就没有必要继续整除，可以得出结论，A一定是质数。