|
用偶数和式间接求素数
偶数2n表示为两整数m和(2n-m)的和2n=m+(2n-m),素数p不大于(2n)^0.5,(2n-m)表示的整数中去掉p的倍数、余下的数是素数。(2n-m)表示数中去掉p的倍数即是在1到m中的整数中去掉与2n模p同余的数。
例:2n=30,p=2、3、5<30^0.5,
m=1、2、3、4、5、5、6、7、8、9、10、11、12、13、14、15. 去2的倍数得
1、3、5、7、9、11、13、15. 去3的倍数得
1、5、7、11、13 去5倍数得
1、7、11、13.
30-m=29、23、19、17.
2n=60,p=2、3、5、7<60^0.5,在m表示的数中去掉2、3、5的倍数得
m=1、7、11、13、17、19、23、29,60除以7余4,去除以7余4的数得
m=1、7、13、17、19、23、29.
60-m=59、53、47、43、41、37、31.
2n=120,p=2、3、5、7<120^0.5,在m表示的数中去2、3、5的倍数得
m=1、7、11、13、17、19、23、29、31、37、41、43、47、49、53、59,120除以7余1,去除以7余1的数得
m=7、11、13、17、19、23、31、37、41、47、49、53、59.
2n-m=113、109、107、103、101、97、89、83、79、73、71、67、61.
2n=32,p=2、3、5<32^0.5,在m表示的数中去除以2、3、5余0、2、2的数得
m=1、3、9、13、15
2n-m=31、29、23、19、17.
2n=62,p=2、3、5、7<62^0.5,在m表示的数中去除以2、3、5、7余0、2、2、6的数得
m=1、3、9、15、19、21、25、31.
2n-m=61、59、53、47、43、41、37、31.
2n=122,p=2、3、5、7、11<122^0.5,在m表示的数中去除以2、3、5、7、11余0、2、2、3、1的数得
m=9、13、15、19、21、25、33、39、43、49、51、55、61.
2n-m=113、109、107、103、101、97、89、83、79、73、71、67、61.
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-12-27 08:12
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社