数学建模社区-数学中国

标题: 合数公式 (判断素数或寻找合数因数对) [打印本页]

作者: hmz20128 时间: 2012-12-24 16:08
标题: 合数公式 (判断素数或寻找合数因数对)
在自然数列中，除了0、1以外，不是素数就是合数，每个素数与合数都有其固定的位置，而合数存在规律(任意数n后面的第m个n项仍被n整除，例n=5在5后面的m(1.2.3……m)个5项，即：5+1*5、5+2*5. 5+3*5……5+m*5仍被5整除)，并且所有的合数都能联系在一起，形成一个等差数列网，这个网，呈上小下大的金字塔状，也可以说像树根状，如果把这个网从自然数列中抽出来，剩下的素数就没有规律了。相当于把一个形如树根的多串相连的珠子放进广口瓶中，然后用黄豆填满(填充的特点是下面豆子少上面的豆子多)，豆子与珠子各有自己的位置，根据所处位置看其是否被线串上，就知道是珠子还是豆子，如果把连在一起的多串珠子抽出来，剩下的豆子就看不出规律了，也就是豆子的使命是填充珠子没有占完的位置。自然数列中的项数就是合数与素数的位置，某一项只要不是合数就一定是素数。因此，要判断素数就要根据某数的特点，看是否存在于合数的等差数列网上，在网上的就是合数，不在网上的就是素数。

下面是一个根据合数的网式规律而得到的最基本的合数公式(即：判断任意数)

M=(q-N)/(2*N+1) 其中q是常量，表示被判断数I被2除的整数商(例：I=31，I/2的整数商为15，即：q=15)，M、N是变量，通过自变量N(N小于I的平方根取整加1，例：被判断数I=31，I的平方根取整是5，则N的最大值是5+1=6)的非负整数取值，判断M是否为非负整数，若M出现非负整数，则I是合数，并且非负整数M、N能满足(2*M+1)和(2*N+1)是I的一个因数对，在适合条件的范围内有多少对M、N适合条件，就说明I有多少个因数对。在适合条件的范围内，没有一对M、N同时满足非负整数，就说明I是素数。
例1：I=27
因为I=27除以2的整数商为13
则：由合数公式M=(q-N)/(2*N+1)得：
M=(13-N)/(2*N+1)
N的最大值为：I=27的平方根取整加1，即：5+1=6
当N=1时M=(13-1)/(2*1+1)=4
则：(2*M+1)=(2*4+1)=9
(2*N+1)=(2*1+1)=3
即：(2*M+1)=9和(2*N+1)=3是I=27的一个因数对。
同理：当N=2、3、4、5、6时
只有当N=4时，才能得到非负整数M=1
即：(2*M+1)=(2*1+1)=3
(2*N+1)=(2*4+1)=9
与前面的(2*M+1)=9和(2*N+1)=3正好相反
则：说明I=27只有一个因数对3*9(因数为1除外)
例2：I=31
因为I=31除以2的整数商为15
则：由合数公式M=(q-N)/(2*N+1)得：
M=(15-N)/(2*N+1)
N的最大值为：I=31的平方根取整加1，即：5+1=6
当N=1、2、3、4、5、6时
没有一个N能使M为非负整数
所以I=31是素数。
数海聚珠网【程序体验】中的19、20、21号程序，就是利用合数公式得到的：
1、精确判断素数计算素数个数，及寻找合数因数对
2、精确计算哥猜数对
3、精确计算孪生素数对并计算孪生素数对个数

*用19号程序：判断素数、合数及寻找合数的所有因数对，并且最后输出范围内合数、素数的个数。

下面寻找的是形如30*n+17且n在111111111-111111999之间的素数、合数及合数的所有因数对，并且最后输出范围内合数、素数的个数。
输入：
用第二选项，E=17，h=111111111,，L=111111999，
先点击：并行参数开始，有数据出现，再点击：结果开始。
(T下面有X、Y值的就是合数，并且X、Y是T的所有因数对，没有X、Y出现的T是素数。最后输出的是在范围内，素数与合数的个数。由于较多，数据中间使用了省略号)
T=33333333347
T=33333333377
T=33333333407
  X=3030303037
  Y=11
  X=628930819
  Y=53
  X=57175529
  Y=583
T=33333333437
  X=254452927
  Y=131
  X=16347883
  Y=2039
  X=267109
  Y=124793
T=33333333467
  X=4761904781
  Y=7
  X=709219861
  Y=47
  X=311526481
  Y=107
  X=138312587
  Y=241
  X=101317123
  Y=329
  X=44503783
  Y=749
  X=19758941
  Y=1687
  X=8483923
  Y=3929
  X=6628223
  Y=5029
  X=2942821
  Y=11327
  X=1292641
  Y=25787
  X=1211989
  Y=27503
  X=946889
  Y=35203
  X=420403
  Y=79289
  X=184663
  Y=180509
……
T=33333335867
  X=2564102759
  Y=13
T=33333335897
  X=2886253
  Y=11549
T=33333335927
  X=900900971
  Y=37
  X=1191881
  Y=27967
  X=1034779
  Y=32213
T=33333335957
  X=1754386103
  Y=19
T=33333335987
  X=4761905141
  Y=7
  X=680272163
  Y=49
合计：89个
素数：11个
合数：78个

若再选择第三种输出方式（输出的是所有素数及个数）
即：
T=33333333347
T=33333333377
T=33333333647
T=33333333827
T=33333333857
T=33333334007
T=33333334487
T=33333334907
T=33333335027
T=33333335177
T=33333335657
素数：11个

*使用20号程序:寻找哥德巴赫猜想数对

用30n+11 与30n+23 组成的哥猜偶数30n+4(n最小为1)在1<n<111
输入：E1=11，E2=23，h=0，L=111
输出：
34有1对
(11,23)
64有2对
(11,53)
(41,23)
94有3对
(11,83)
(41,53)
(71,23)
124有4对
(11,113)
(41,83)
(71,53)
(101,23)
154有4对
(41,113)
(71,83)
(101,53)
(131,23)
184有4对
(11,173)
(71,113)
(101,83)
(131,53)
214有4对
(41,173)
(101,113)
(131,83)
(191,23)
……
3324有24对
(73,3251)
(103,3221)
(283,3041)
(313,3011)
(463,2861)
(523,2801)
(613,2711)
(733,2591)
(883,2441)
(1213,2111)
(1423,1901)
(1453,1871)
(1723,1601)
(1753,1571)
(1873,1451)
(2143,1181)
(2293,1031)
(2383,941)
(2503,821)
(2683,641)
(2803,521)
(2833,491)
(3253,71)
(3313,11)

*使用21号程序：寻找孪生素数对

用30n+11 与30n+13 组成的孪生素数n在111111111<n<111111999，
在程序中输入：E1=11，E2=13，h=111111111,，L=111111999
输出：
3333334391,3333334393
3333335771,3333335773
3333336701,3333336703
3333337661,3333337663
3333338711,3333338713
3333339701,3333339703
3333340391,3333340393
3333342401,3333342403
3333342581,3333342583
3333343421,3333343423
3333345011,3333345013
3333346061,3333346063
3333346571,3333346573
3333349751,3333349753
3333350201,3333350203
3333350261,3333350263
3333350651,3333350653
3333351641,3333351643
3333353531,3333353533
3333355601,3333355603
3333358211,3333358213
3333358361,3333358363
3333358781,3333358783
3333359501,3333359503
3333359591,3333359593
3333359831,3333359833
共有26对

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)