如何算出质数的好方法

⑴ 如何判断质数

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

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的倍数。

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

⑵ 如何判断质数的方法

判断一个数是否为质数，常见的方法有以下几种：

1. 最大因数法：

   • 尝试寻找一个数的最大因数。
   • 若该数的最大因数为它本身，则为质数。

2. 平方根法则：

   • 计算该数的平方根，取其整数部分。
   • 若整数部分大于1且小于该数本身，则该数非质数。
   • 若整数部分小于等于1，则该数为质数。

3. 因子表法：

   • 构建一个从2到该数平方根的因数表。
   • 检查该数是否有除1和自身外的因数。
   • 若无，则该数为质数。

注意：以上方法适用于多数情况下的质数判断。在处理较大数时，由于计算量较大，可以使用更高效的算法，如米勒拉宾素性检验、费马检验等。