数学建模社区-数学中国

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

作者: 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整除),并且所有的合数都能联系在一起,形成一个等差数列网,这个网,呈上小下大的金字塔状,也可以说像树根状,如果把这个网从自然数列中抽出来,剩下的素数就没有规律了。相当于把一个形如树根的多串相连的珠子放进广口瓶中,然后用黄豆填满(填充的特点是下面豆子少上面的豆子多),豆子与珠子各有自己的位置,根据所处位置看其是否被线串上,就知道是珠子还是豆子,如果把连在一起的多串珠子抽出来,剩下的豆子就看不出规律了,也就是豆子的使命是填充珠子没有占完的位置。自然数列中的项数就是合数与素数的位置,某一项只要不是合数就一定是素数。因此,要判断素数就要根据某数的特点,看是否存在于合数的等差数列网上,在网上的就是合数,不在网上的就是素数。
: J5 W: M. W& r* G; k) a2 C1 l5 A; ~# C* R; w  u
下面是一个根据合数的网式规律而得到的最基本的合数公式(即:判断任意数)! W# p% K( D; g' s; C; G* Z. h8 G

! p6 F( I9 [/ T( r; f7 fM=(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是素数。' |3 k3 b' h. H
例1:I=27
8 ]7 C  |: o. h% N& \- h因为I=27除以2的整数商为13
7 i5 u8 g" \  l( Q2 q. C" t# W, u* q6 ~则:由合数公式M=(q-N)/(2*N+1)得:
7 k* K$ `2 W7 r& U( b4 F5 \2 L; GM=(13-N)/(2*N+1)
4 {3 `: Z' g* ^6 T: rN的最大值为:I=27的平方根取整加1,即:5+1=6* H' g' J3 ~+ z( c+ }0 I$ X/ w; q
当N=1时M=(13-1)/(2*1+1)=40 A) M  y6 l1 \, u) c' n  g
则:(2*M+1)=(2*4+1)=97 x' R7 x. I* U
(2*N+1)=(2*1+1)=38 ^$ v" p) m9 F+ F% @+ S8 w6 W/ A
即:(2*M+1)=9和(2*N+1)=3是I=27的一个因数对。- @' c4 N( w6 Y+ l/ I" K
同理:当N=2、3、4、5、6时$ s* j: j8 r9 G$ w/ S
只有当N=4时,才能得到非负整数M=1
% V8 O# o* \' c6 ~7 |即:(2*M+1)=(2*1+1)=3
; O6 v" ^" `$ V" }(2*N+1)=(2*4+1)=9* d5 i# d8 Z1 N* U
与前面的(2*M+1)=9和(2*N+1)=3正好相反( ]3 d3 a& z" v( V: b5 V. ~
则:说明I=27只有一个因数对3*9(因数为1除外)
, X) Q( Y: @9 ~( s* `例2:I=31
% {% h' Z9 I; t, O: T. S7 G3 ]因为I=31除以2的整数商为157 H# H; E6 F" l2 w
则:由合数公式M=(q-N)/(2*N+1)得:
+ {& n1 x  t1 d! W2 O( A* kM=(15-N)/(2*N+1) 0 g% q# \# z2 S' a7 D
N的最大值为:I=31的平方根取整加1,即:5+1=6/ }; G( P3 a$ O
当N=1、2、3、4、5、6时' B+ s! i1 f# H) _2 Y4 q  i/ C8 E0 ?
没有一个N能使M为非负整数0 @4 Q& y/ O0 t/ ]9 c# p7 Z
所以I=31是素数。
( y% a2 g8 a# B, B3 J数海聚珠网【程序体验】中的19、20、21号程序,就是利用合数公式得到的:. S8 S; S+ n. Q) g- N8 }/ Y6 c3 H
1、精确判断素数计算素数个数,及寻找合数因数对
' H2 c. x2 T0 l+ M8 X2 i! f0 g* i2、精确计算哥猜数对$ |5 j* v1 U' Q( r/ Z5 N  ?# g$ n
3、精确计算孪生素数对并计算孪生素数对个数
' D3 J1 X% e* s) X, R( _# a( h! Z5 j+ i/ z' Q0 f
*用19号程序:判断素数、合数及寻找合数的所有因数对,并且最后输出范围内合数、素数的个数。! `. |! a; i3 v: D2 u5 M

3 K# a& H2 X; T" I下面寻找的是形如30*n+17且n在111111111-111111999之间的素数、合数及合数的所有因数对,并且最后输出范围内合数、素数的个数。  j: z( q8 `8 x$ A8 t
输入:
# Z3 Y4 {+ v1 S用第二选项,E=17,h=111111111,,L=111111999,9 ]5 }3 ?' B' B; J
先点击:并行参数开始,有数据出现,再点击:结果开始。
& I) E7 ?+ U( N7 A, F# s/ B5 Z. N4 Z2 D(T下面有X、Y值的就是合数,并且X、Y是T的所有因数对,没有X、Y出现的T是素数。最后输出的是在范围内,素数与合数的个数。由于较多,数据中间使用了省略号)2 h3 u$ d7 V9 N
T=33333333347
5 ~! I% r; M, Y; HT=33333333377  Z& M7 @  ]7 O+ {, j
T=333333334077 w& r/ L6 y" b' Z, l
  X=3030303037
- W  s3 c2 `5 k& J- e  Y=11
! X7 R. u6 R  D" l, c/ W+ Y  X=628930819
6 p8 |0 E) j0 S  Y=53
* t3 p, P4 }. h. `# |4 L  }5 g  X=57175529
  e  P, |! `8 Y  _  Y=583
" o; Z4 Z( [( @, x, M4 rT=33333333437
& T" ~/ Q4 ~3 B$ s* B8 _  X=2544529272 f7 j; i4 {! j7 c
  Y=131! s, d: ^* z# X. M# q2 t' Q" A1 F
  X=16347883
) ^- b+ ~2 }; n5 T, Z+ Y: H  Y=2039. R* _6 d8 n: p+ H5 @) T2 ~
  X=267109
# S4 w7 Y% ?' s" d) I  Y=124793
( H: e# C% T4 n6 f! P2 `T=33333333467! A7 a% R  n% U1 L) v- L  u
  X=4761904781
, V) x" r' P+ E0 k  Y=7
, f9 C; g0 H1 l* I  X=709219861
8 o' n, w# m6 Y% n* ^2 I  Y=47- y2 T. ^" r9 a$ w
  X=311526481
" S1 f; Z3 W1 n! x  Y=107. Z- B  A2 f3 B4 K7 B3 b5 _. ~
  X=1383125870 z& r' m$ ^, f+ U: ]4 D7 ~) C, o
  Y=241
- q* F5 A* r  j$ Z) c! l! N0 Z  X=1013171230 j* J4 d/ `8 ]" c: F( S$ j
  Y=329
7 h% e4 z/ A( P! o# t  X=44503783
# p8 T, i7 _# V7 y3 d( j/ p# T' W  Y=749
) A4 c' i! L) ]3 [, n  X=19758941+ }: c+ ^2 {4 _% X4 [
  Y=1687% q. y8 M6 o, [$ r# `
  X=8483923
* s- N. h$ g; n9 n) g* n  Y=3929
- ?3 t2 g& g/ d+ z  X=6628223* L# a+ y3 q9 b+ r9 \$ a
  Y=5029
: H$ f' r$ I. i/ @) w  X=2942821
9 k+ a* _& D( a" i, D" k/ I  Y=11327
3 ]( p6 t- Q7 P& a1 h! a, M1 M  X=1292641# V# t, G# d3 C" e1 I4 o# }
  Y=25787
. m2 T# v9 K+ y. l# z( u  X=1211989
# P( p$ z6 E- R, x3 D1 k6 o  Y=27503- a0 X7 k7 E- N' C% \! T- Y& R7 Z
  X=946889
9 \2 }6 [4 I% p+ W+ U  Y=352036 |# {3 b  U- C" Z- Q, ^+ a& y
  X=4204037 \: [0 s! s. @1 ^+ L! V, H
  Y=79289) C7 k; I# i+ F. n! d. @7 A
  X=1846639 q+ Y. b5 A3 C8 }6 Z
  Y=180509
3 I3 S# x& t$ X……
" }2 h7 c9 T) N, {. m9 WT=33333335867
+ [% g7 F0 K, ~/ a( v+ r  X=2564102759
  z& X( Z: ?" z; y- F* [$ z. j  Y=13
. k6 A4 j9 z. JT=333333358974 q4 S6 X/ P8 k2 s9 M" Q
  X=2886253
# ^% f' g' i6 U8 W8 r( Y  Y=11549) N0 V" G# i# x+ f) s" A$ e
T=33333335927
; O2 I/ F2 B4 o" i; o( Q  z  X=900900971. O2 R% d; A+ U* V9 k: z# r( V
  Y=37
  C# X7 U5 f6 \# K% _  X=1191881
( i5 i+ x6 m& n% ^% i3 a1 i* i7 R  Y=279679 S/ Y5 ?$ B( M$ g- Q. W5 P: x
  X=1034779
6 Z; \# v+ l: a) Q: k  n  Y=32213+ |! w; d, T. N) U+ P+ X
T=33333335957! Y- T2 x8 L! ]' n
  X=1754386103
* ], m. s. U( E) l  Y=192 I$ }6 H4 U% U: Q4 C, ?5 ]- Z, x4 {
T=333333359876 v4 p" l( m' E% _  g6 v" ?
  X=4761905141
# d' q& ^& G. d1 T6 x: P& ^# `+ ?  Y=7
; R, X' S9 X/ y  X=680272163+ I/ a9 B/ [1 l7 }/ n, G
  Y=49% ^, Y* P1 `" W
合计:89个
" l/ L  V# c) o# _    素数:11个
% J' _: P8 O& s' b1 I2 y1 m    合数:78个3 {0 h1 r" g3 ?* D

% Y( O+ _7 J5 K" K  T4 {若再选择第三种输出方式(输出的是所有素数及个数)$ |& V) O2 e' T) r7 F  p5 {$ X% r* h
即:
: ^  V  w4 @3 tT=33333333347
5 f) o' J3 o; H( X1 uT=33333333377. J" P* H5 ~  D) \
T=333333336478 }) t/ U+ u( R( @6 K$ }* \
T=33333333827* }# i0 e& y4 z5 C
T=33333333857
6 p/ y; {3 J# @9 E: ST=33333334007
. p# V7 E* ]  I3 @. {: wT=33333334487
+ u+ v0 b7 g  hT=33333334907
) L* A5 _9 X% Z4 @6 c4 H2 vT=333333350270 u+ ~" V7 q3 J0 O' W& r0 X
T=33333335177
3 g1 a9 v! q: m/ }. ?. oT=33333335657
- I7 ]0 o5 Y. n: V& e+ Q素数:11个$ p8 }( L& m1 K" E+ u8 @+ \

. h$ M) _6 _& Y, \' ^, T/ f& N; M*使用20号程序:寻找哥德巴赫猜想数对
8 }! y5 t9 b# d! q+ T& J0 J: ~. `
9 U# `* n) }2 n& s5 n0 f5 O: R2 `用30n+11 与30n+23 组成的哥猜偶数30n+4(n最小为1)在1<n<111/ G4 O: @3 N4 K
输入:E1=11,E2=23,h=0,L=111; j1 y3 p( z5 u8 ~1 D4 a
输出:
% i, H6 r' h0 |! @% `$ Q34有1对: s' O& Z, {0 j2 i2 R7 g
   (11,23)) x5 ]6 H# V9 o9 y# J6 z
64有2对
, ^) [/ S! i: \( X9 m8 T0 J, F   (11,53)3 Y2 d% S$ I" Q* r5 @# F& w
   (41,23)3 {4 F6 }; x& i7 I: I9 R
94有3对, ~$ s5 a/ l! H! m3 y! }9 [
   (11,83)
0 v4 R8 \- k4 @  y- y) A   (41,53)
5 w9 |! W4 j8 c7 k8 b8 o0 h5 p   (71,23)6 t  S# ~& z5 f4 Y
124有4对
7 d) b9 V5 I0 ?4 j2 |) B   (11,113)# |+ T! F) S; b$ x. d8 B
   (41,83)
! k4 X5 P! d9 z9 \4 P8 M   (71,53)
" j- j3 v! H- w: j3 ^4 }& n   (101,23)9 u* {. C1 t: I; r2 e8 j' c6 |
154有4对
; Y. j+ P( R. H: u   (41,113)
( E! }/ M0 @! F8 A8 V, B/ ~  j' v   (71,83)* f: v* c4 M$ e5 y9 K# h! t4 @
   (101,53), c. G- `7 h0 y( M
   (131,23)
  \! `7 R; `" E184有4对# w$ u. y+ r+ n9 j: W9 [& U
   (11,173)
( R) d5 v- N4 m/ W$ W* E* l2 Q   (71,113)1 M: \! D& e" [$ e' q) _
   (101,83)6 T1 q, l4 O& K( N) ^- p
   (131,53)4 S/ ?: [8 s+ j; W/ c
214有4对! Z3 u1 w6 D, ~' {+ W
   (41,173)$ G; J% Z- V( G7 ~# {; E
   (101,113)
1 z+ d3 E9 G7 `' K" h& |/ V' J5 d- }3 b, v   (131,83)2 u, X& U1 Z8 u+ u' ~9 [5 x7 Z
   (191,23)# m8 R3 S5 T% S8 T3 c
……
6 e# [, q1 X0 |& R4 ]: I3324有24对" g3 {, \; a1 d- q
   (73,3251)
& |$ N6 y4 ?: V& H   (103,3221)
( P+ F9 z' E- x9 a" e! x   (283,3041)# ?3 m" B$ ~1 p& v' ~7 S5 p+ x
   (313,3011)
. Y- h' |( t6 F1 R   (463,2861)* m8 Z! p6 Y' B& r
   (523,2801)6 H% c( r! C/ p  U  E3 H
   (613,2711)
4 d1 n3 S5 \/ W   (733,2591)
* S- V8 i$ M5 ]4 h   (883,2441)
3 ~$ H5 f  |% J" z3 h1 {   (1213,2111)9 m  t. h8 H( J% i4 N. l
   (1423,1901)6 V# F8 Y6 _4 }0 s! N5 a
   (1453,1871)6 U& x' }  k) x3 t# k. Z% Z- N2 Y8 r3 L! W
   (1723,1601)' H# P+ u5 @6 a4 q8 U+ w' z
   (1753,1571)/ M, `* T$ b0 {( ~: w5 O4 x
   (1873,1451)
. j4 f; E, V2 ^   (2143,1181)) M9 `9 e- b, n, M
   (2293,1031)
8 l7 t! m  B0 J, f, K  _/ ^   (2383,941)
: P( {& e. j- `% {   (2503,821)
9 Z! @8 Y8 q; v* F( W   (2683,641), P9 `% u  S1 F5 P2 v7 ^$ M9 D
   (2803,521)
( f; [8 K) X3 m/ Z   (2833,491)
, F) z  V" V; p6 ?   (3253,71)3 T2 O9 X0 T& j9 @: u' x( l
   (3313,11)' ~% L) j5 d. l8 H, D5 M2 f. F

- y& U7 E$ V, A% h*使用21号程序:寻找孪生素数对" ~; r, p6 D! _' b. ]7 v
% w% |1 U& _6 B7 e, _- o2 a
用30n+11 与30n+13 组成的孪生素数n在111111111<n<111111999,* a/ t. F$ h8 U* G; B2 m
在程序中输入:E1=11,E2=13,h=111111111,,L=111111999; J  O: r; J- W% _8 m" t: ~
输出:& e7 r2 C6 O7 u* O* L, R6 n
3333334391,3333334393  B1 {! q: e) M
3333335771,33333357730 i& ?. `0 F- t
3333336701,33333367035 i, e$ ?. v7 O0 S. B, W
3333337661,3333337663; t* `! d/ Y. C% |4 P- q) e
3333338711,33333387136 W6 h2 a( o. ^& c( _: Q2 \, u0 X
3333339701,3333339703
) O  ], v. X- ]! C3333340391,3333340393. u9 B2 U4 l8 t" Z0 }
3333342401,3333342403/ P- s7 `+ m8 @7 |1 d2 \7 x
3333342581,3333342583
: e) o& h* C& ^6 N7 G7 Y3333343421,3333343423: w0 G4 X9 f7 Q# z% _
3333345011,3333345013
6 z, t3 b1 p' K6 W- e5 E3333346061,3333346063
! N! ^* e) ~6 a9 S3333346571,3333346573
) d$ `1 M5 Y/ q" V" R) }8 S, q3333349751,33333497530 z' J- z# T$ \% x" P( C# M. @
3333350201,3333350203: P; ^$ a3 Y+ [' f$ Q& ~
3333350261,3333350263
' Y2 z' N. e- a* d+ l1 a3333350651,3333350653
0 S$ @9 H5 n9 g' ~. d3333351641,3333351643
* {' n" j( l1 W  U; x3333353531,3333353533& H  W+ }7 R  j$ j7 J- D
3333355601,3333355603
# h/ M7 ]% w1 W3333358211,3333358213; f& ]& M6 D1 F) u
3333358361,3333358363
& j" ?6 a/ S, n9 L& W3333358781,3333358783
" t4 R$ U8 Z) U$ n' ^' F% q9 r9 ^3333359501,3333359503
- Z7 q  ?$ e! i  @, }/ K: c3333359591,33333595933 X2 c/ G$ F. Y% _4 n3 _/ Z& Z
3333359831,3333359833
6 E- \7 x. }- m" z8 G共有26对. ?2 e% A& S6 P8 C
0 F/ E5 P( T0 F- S





欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5