||
创建一种判断素数的简便方法
所有的偶数都可被2整除,就不是素数,因此:
末位数为:2、4、6、8、0,的任何整数,就都不是素数。
末位数不是:2、4、6、8、0,的任何整数,就可能是素数。
5与任何数相乘,其末位数必为:5或0,因此:
末位数为:5和0的任何整数,就都不是素数。
末位数不是:5和0的任何整数,就可能是素数。
对于末位数为:1、3、7、9的任何整数,则:
3与任何数相乘,其各位数之和,都必可被3整除,就不是素数,因此:
各位数之和可以被3整除的整数,就都不是素数。
各位数之和不可被3整除的整数,就可能是素数。
若不能被3整除:
且其各位数都是7,可被7整除,就不是素数。
且其各位数不都是7,不可被7整除,就可能是素数。
若其各位数不都是7,而末位数为7,则,去掉其末位数后,减2,如前,判断其是否能被 9或3整除;若能,该整数就能被9或3整除,若不能,其末位数,又为7,则重复如上做法;直到最后只剩下2位数,若=27,则该整数就能被3或9整除,就不是素数。
若以上各种情况,都不成立,
且其末位数为3,则,去掉其末位数后,减6,如前,判断其是否能被 7或9整除;若能,该整数就能被7或9整除,若不能,其末位数,又为3,则重复如上做法;直到最后只剩下2位数,若=63,则该整数就能被7或9整除,就不是素数。
若以上各种情况,都不成立,
且其末位数为9,则,去掉其末位数后,减4,如前,判断其是否能被 7整除;若能,该整数就能被7整除,若不能,其末位数,又为9,则重复如上做法;直到最后只剩下2位数,若=49,则该整数就能被7整除,就不是素数。
若以上各种情况,都不成立,
且其末位数为1,则:
去掉其末位数后,减2,判断其是否能被3或 7整除;若能,该整数就能被3或7整除,若不能,其末位数,又为1,则重复如上做法;直到最后只剩下2位数,若=21,则该整数就能被3或7整除,就不是素数。
若以上情况都不成立,就可能是素数。
而且,对于高位数的整数,还必须考虑到是否能被更高位数的素数整除,例如:
末位数=1的 221 可被 13,17 整除;
末位数=3的 553 可被 29,17 整除;
末位数=7的 187 可被 11,17 整除;
末位数=9的 2299 可被 11,19 整除;等等,都须具体判定。
正因以上方法尚未解决判定是否能被大于11的各素数整除,就必须限制于整数小于121,才能得出:
任何整数,只要以上各种情况,有任何一种成立,就不是素数,如果所有情况都不成立,就必是末位数=1,3,7,9的素数。
虽然,还可以给出更多的条件,增大必须限制小于的数值,但是,这个数值不可能无穷大。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-24 03:53
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社