合数公式 (判断素数或寻找合数因数对)

hmz20128

在自然数列中，除了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整除)，并且所有的合数都能联系在一起，形成一个等差数列网，这个网，呈上小下大的金字塔状，也可以说像树根状，如果把这个网从自然数列中抽出来，剩下的素数就没有规律了。相当于把一个形如树根的多串相连的珠子放进广口瓶中，然后用黄豆填满(填充的特点是下面豆子少上面的豆子多)，豆子与珠子各有自己的位置，根据所处位置看其是否被线串上，就知道是珠子还是豆子，如果把连在一起的多串珠子抽出来，剩下的豆子就看不出规律了，也就是豆子的使命是填充珠子没有占完的位置。自然数列中的项数就是合数与素数的位置，某一项只要不是合数就一定是素数。因此，要判断素数就要根据某数的特点，看是否存在于合数的等差数列网上，在网上的就是合数，不在网上的就是素数。

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

% Z; @& |" r8 p! C/ `% SM=(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是素数。
# U$ v1 I: l) x1 V3 S4 X" t$ Q例1：I=27
# H, z# V: u. c4 h6 U  W因为I=27除以2的整数商为13
则：由合数公式M=(q-N)/(2*N+1)得：
9 q+ m  I2 g* x# B6 ^2 f/ G& ~M=(13-N)/(2*N+1)
4 `$ L2 S9 L) K& FN的最大值为：I=27的平方根取整加1，即：5+1=6
6 A  R7 L& }- G; ^, I! J2 R) j& c4 l当N=1时M=(13-1)/(2*1+1)=4
则：(2*M+1)=(2*4+1)=9
(2*N+1)=(2*1+1)=3
# \8 O" i4 Q& N+ i) A, H即：(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
' c3 j" h7 t' x3 c8 ^& g0 u  J2 u与前面的(2*M+1)=9和(2*N+1)=3正好相反
则：说明I=27只有一个因数对3*9(因数为1除外)
例2：I=31
' }2 D. C4 p4 G$ M) O* p% R2 B因为I=31除以2的整数商为15
/ G8 c; F2 V9 D* w$ e则：由合数公式M=(q-N)/(2*N+1)得：
M=(15-N)/(2*N+1)
N的最大值为：I=31的平方根取整加1，即：5+1=6
. a' C! i' l( ?. C8 z当N=1、2、3、4、5、6时
7 F1 J, K! Y  o2 f& c, Y9 G/ w没有一个N能使M为非负整数
$ L3 C) D8 B5 W2 l所以I=31是素数。
# l" p3 T: R; q. G数海聚珠网【程序体验】中的19、20、21号程序，就是利用合数公式得到的：
1、精确判断素数计算素数个数，及寻找合数因数对
2、精确计算哥猜数对
3、精确计算孪生素数对并计算孪生素数对个数

, K: m' a+ v- U6 f# B*用19号程序：判断素数、合数及寻找合数的所有因数对，并且最后输出范围内合数、素数的个数。
: Y, G7 R  X9 M" j/ s
下面寻找的是形如30*n+17且n在111111111-111111999之间的素数、合数及合数的所有因数对，并且最后输出范围内合数、素数的个数。
输入：
: g$ Q, n2 P& [  z7 m! Y: l用第二选项，E=17，h=111111111,，L=111111999，
先点击：并行参数开始，有数据出现，再点击：结果开始。
(T下面有X、Y值的就是合数，并且X、Y是T的所有因数对，没有X、Y出现的T是素数。最后输出的是在范围内，素数与合数的个数。由于较多，数据中间使用了省略号)
. `7 E0 {8 b& l$ Z& X) U& XT=33333333347
T=33333333377
T=33333333407
4 d* d2 b* o& f5 Q  X=3030303037
  Y=11
  X=628930819
3 x$ {- g  K: r0 W1 g4 k# `9 J  Y=53
( T6 b5 n" `* g3 o% O9 B! k; G  X=57175529
  Y=583
* o& U( h. M! BT=33333333437
  X=254452927
0 M! ~. y5 y( ]* i" d) D. Z8 d  Y=131
  X=16347883
: ?9 Z7 I' H, v+ }  Y=2039
  X=267109
  Y=124793
# s# w" q9 p* _# ~, {0 g* @2 V! _T=33333333467
  X=4761904781
  Y=7
  X=709219861
2 K3 R2 b6 s( I- Z5 k9 y2 \( t  Y=47
! H- j/ K2 c# o8 [# B' \  X=311526481
6 ?, ?( i, t3 a1 c7 i6 P  Y=107
  X=138312587
  E8 W( z; I: `4 C- P; A6 r8 s  Y=241
% D0 G+ D1 Y" {  ^  X=101317123
  Y=329
  X=44503783
  Y=749
) o, y0 M( c7 U2 k. h5 ]  X=19758941
  Y=1687
+ n. j' ?. }: Y$ `" W, F9 Z  X=8483923
  Y=3929
9 B$ A& v! f* [  o  S  X=6628223
  Y=5029
2 N& A+ o: Z. Y1 l6 b4 r  X=2942821
  Y=11327
  X=1292641
) V2 q! F9 U5 N7 D  W  e( H) i  Y=25787
  V4 q5 w: f# y# p- D# D1 {  X=1211989
  Y=27503
1 }% |& P4 A0 `; s, @$ v( V3 `/ y  X=946889
4 V! t9 x; M+ h( a  Y=35203
9 S8 K6 V6 o" _& R- \: p  X=420403
  Y=79289
* h7 m( D, U- Q: W( f  X=184663
  Y=180509
……
T=33333335867
1 X8 V! Y; S% `3 \$ ~! b5 b  X=2564102759
  Y=13
5 a3 j0 k: a6 v8 ?T=33333335897
  X=2886253
  Y=11549
; J  _; f6 }0 O- f4 iT=33333335927
  X=900900971
  Y=37
3 d2 g/ j( c/ A; t2 X. ~  X=1191881
# @3 ]( P7 U( G$ E# }5 S2 c5 |  Y=27967
  X=1034779
  Y=32213
T=33333335957
  X=1754386103
% e' ?$ K. ~& v) B' p# }5 ^  Y=19
T=33333335987
  X=4761905141
  Y=7
" I; A4 R* G: R8 ^3 f  o& c* m  X=680272163
% A9 P8 X: ?$ T  Y=49
1 ?$ }7 v/ P# t: Y' Z合计：89个
  [/ K+ X7 `+ w& \; ~% P8 ~    素数：11个
( ~8 ^3 ~  h2 o% H" h7 }    合数：78个
; A5 M) H- s" K0 ^
若再选择第三种输出方式（输出的是所有素数及个数）
! h4 b. Z8 Z% o7 U1 u即：
T=33333333347
T=33333333377
T=33333333647
T=33333333827
. F; e- y- v: G' J  xT=33333333857
T=33333334007
7 g% r  F% y# wT=33333334487
T=33333334907
T=33333335027
T=33333335177
T=33333335657
0 T8 \% p  x0 C/ v- n素数：11个
( O: w! z5 f. S, p
8 C; n/ J5 y& M1 |*使用20号程序:寻找哥德巴赫猜想数对
4 X  k# ~5 w; T
$ _6 y4 l- |4 t" t用30n+11 与30n+23 组成的哥猜偶数30n+4(n最小为1)在1<n<111
输入：E1=11，E2=23，h=0，L=111
* h$ z' i, q5 c输出：
34有1对
$ D" b# r' S, K; K   (11,23)
64有2对
0 W; {5 c9 @& \: t   (11,53)
$ J# X- [7 j7 ?   (41,23)
94有3对
   (11,83)
   (41,53)
   (71,23)
! V8 N# U" m, Q6 r9 Y124有4对
4 c# X$ e- w4 G* w   (11,113)
   (41,83)
   (71,53)
   (101,23)
154有4对
   (41,113)
   (71,83)
   (101,53)
$ o7 s+ J8 p9 W; V9 \" y) s   (131,23)
. r9 \# _# s: W. v& O184有4对
' h/ }! ~" X/ S# N   (11,173)
8 p( |. {8 I6 q& e) W) c+ C   (71,113)
   (101,83)
- g2 ?+ T! N. m; F' k  j8 o   (131,53)
214有4对
7 ]& I9 g( f1 Z0 c   (41,173)
4 P3 `7 F# E, V- E. m   (101,113)
( g" w7 ~% D/ h   (131,83)
! N& M0 S# R, N# `: q- v5 T2 p% s   (191,23)
……
$ F# n! v. o; e: N! F9 {; b% v3324有24对
   (73,3251)
   (103,3221)
   (283,3041)
, [8 J( D+ n5 Y1 P   (313,3011)
   (463,2861)
: v4 {5 W5 ?7 u4 U: N. Z/ m0 L   (523,2801)
   (613,2711)
   (733,2591)
/ P4 d3 Q* ]8 T$ I   (883,2441)
   (1213,2111)
$ s3 I- H1 f9 ?; k   (1423,1901)
; s; N7 s7 Q- y, t7 Z% |   (1453,1871)
   (1723,1601)
   (1753,1571)
   (1873,1451)
   (2143,1181)
& L/ }3 N  r' q0 m% l) V   (2293,1031)
   (2383,941)
5 Z; Q7 O" K. P3 _, T" J$ a  I   (2503,821)
   (2683,641)
   (2803,521)
   (2833,491)
   (3253,71)
3 c6 M* {/ T2 d4 s& `& k   (3313,11)

, A2 A; A  b( n, c8 g' a5 ^*使用21号程序：寻找孪生素数对
8 D% T7 ~5 P0 i5 f$ J, i! R
用30n+11 与30n+13 组成的孪生素数n在111111111<n<111111999，
+ T4 ?7 _8 P& k4 G在程序中输入：E1=11，E2=13，h=111111111,，L=111111999
输出：
( B* Q3 v  l1 G6 R0 p0 t: J3333334391,3333334393
3333335771,3333335773
3333336701,3333336703
5 N2 M/ J6 ?  Z1 u8 w" v; R6 l4 E3333337661,3333337663
6 l5 s0 {) x, z3333338711,3333338713
3333339701,3333339703
! W8 Z8 f0 M# s( t3 F3 Q. Z3333340391,3333340393
* H* X" q- c* p1 T+ B  `3333342401,3333342403
3333342581,3333342583
! j; N  n6 `: t6 N7 a" z3333343421,3333343423
3333345011,3333345013
3333346061,3333346063
3333346571,3333346573
3333349751,3333349753
9 b" N& {( a0 ^. T  ^0 r3333350201,3333350203
$ k) f$ C3 G; u+ v1 a+ e  ^3333350261,3333350263
3333350651,3333350653
( \; }! p1 Z! p7 h8 x. @3333351641,3333351643
3333353531,3333353533
3333355601,3333355603
3333358211,3333358213
) x0 G4 E6 }0 c3333358361,3333358363
/ |5 o0 c. z2 S: u3333358781,3333358783
3333359501,3333359503
: m: W2 A' u" e7 P2 f; i3333359591,3333359593
" ]- e1 S7 T9 y7 y$ R3 P3333359831,3333359833
# m; r+ V: ^' j) D1 \& C6 G/ _共有26对