判断质数的最快方法如下:
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的倍数。
第三秒,机动时间、检查时间。