Question

怎样快速判断质数？

Answer 1

判断质数的最快方法如下：

1、查表法：

主要是指查“质数表”。

编制质数表的过程是：按照自然数列，第一个数1不是质数，因此要除外，然后按顺序写出2至100的所有自然数，这些数中2是质数，把它留下，把2后面所有2的倍数划去，2后面的3是质数，接着再把3后面所有3的倍数划去，如此继续下去，剩下的便是100以内的全部质数。

2、试除弊知圆法：

在手头上没有质数表的情况下，可以用试除法来判断一个自然数是不是质数。例如判断143、179是不是质数，就可以按从小到大的顺序用2、3、5、7、11……等质数去试除。一般情况下用20以内的2、3、5、7、11、13、17、19这8个质数去除就可以了。

原理简析：由合数的意义可知，只要判断一个数除了1和它本身还有别的因数，这个数就是合数。因为因数是成对出现的，所以只要判断前一半即可租塌。10^2=100，而10以内的质数只有2、3、5、7，所以只要划掉2、3、5、7的倍数即可（2、3、5、7除外）。

重点来了！2、5的倍数一眼就能看出，3的倍数只需计算数字和（1位数+1位数），7的倍数除去2、3、5的倍数及九九表内的数，只剩下77和91，而77又可以一眼看出是合数，所以只剩一个数——91！

简单归纳一下：100以内除了91，个位数字是1、3、7、9的，数字和不是3的倍数猛搜的都是质数。

举个例子，79

第一秒，不是九九表内数字，不是2、5的倍数，不是77、91；

第二秒，7+9=16，不是3的倍数。

第三秒，机动时间、检查时间。