数学建模社区-数学中国
标题:
合数公式 (判断素数或寻找合数因数对)
[打印本页]
作者:
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整除)，并且所有的合数都能联系在一起，形成一个等差数列网，这个网，呈上小下大的金字塔状，也可以说像树根状，如果把这个网从自然数列中抽出来，剩下的素数就没有规律了。相当于把一个形如树根的多串相连的珠子放进广口瓶中，然后用黄豆填满(填充的特点是下面豆子少上面的豆子多)，豆子与珠子各有自己的位置，根据所处位置看其是否被线串上，就知道是珠子还是豆子，如果把连在一起的多串珠子抽出来，剩下的豆子就看不出规律了，也就是豆子的使命是填充珠子没有占完的位置。自然数列中的项数就是合数与素数的位置，某一项只要不是合数就一定是素数。因此，要判断素数就要根据某数的特点，看是否存在于合数的等差数列网上，在网上的就是合数，不在网上的就是素数。
, Z8 d3 ]% n: v; s. A
$ h/ F8 X2 D1 _8 u; ]" M& W" a
下面是一个根据合数的网式规律而得到的最基本的合数公式(即：判断任意数)
1 K' E( h) n9 y" h
, g- F; [& B* K$ @. [2 z. o
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是素数。
8 ]7 _: J, T% J
例1：I=27
3 A7 q3 |6 e/ ]
因为I=27除以2的整数商为13
. v: C: e# q, Y& B* i
则：由合数公式M=(q-N)/(2*N+1)得：
. _2 n" ?/ H( l
M=(13-N)/(2*N+1)
$ I& p+ @8 e: D: j/ N
N的最大值为：I=27的平方根取整加1，即：5+1=6
7 Q" t; O2 C4 ]$ y- c
当N=1时M=(13-1)/(2*1+1)=4
) T+ F2 ~0 W! d: |
则：(2*M+1)=(2*4+1)=9
% u7 q4 N* Y+ z: ^( e
(2*N+1)=(2*1+1)=3
8 u, E$ B+ b- H) G) N3 A" K
即：(2*M+1)=9和(2*N+1)=3是I=27的一个因数对。
g; Z, K0 Q. c/ R. z
同理：当N=2、3、4、5、6时
! t9 O" Z# h) R& r8 v" a, z( P
只有当N=4时，才能得到非负整数M=1
1 |6 Y& K" D& u' {8 X
即：(2*M+1)=(2*1+1)=3
/ F% D9 f& t) J. I* c
(2*N+1)=(2*4+1)=9
2 J" C( [' O$ _) |6 o/ d5 B
与前面的(2*M+1)=9和(2*N+1)=3正好相反
& \5 K: G4 Y( \
则：说明I=27只有一个因数对3*9(因数为1除外)
8 |% m7 D- x# E" g5 t- l) G
例2：I=31
. j4 l& \0 L5 K, o7 |
因为I=31除以2的整数商为15
) S! v( R# x9 h: d3 r* O8 x
则：由合数公式M=(q-N)/(2*N+1)得：
" J" s# y& w) X# x' @1 `
M=(15-N)/(2*N+1)
7 ^+ ?7 s0 R8 e& d
N的最大值为：I=31的平方根取整加1，即：5+1=6
- H* w! R- G$ h9 J
当N=1、2、3、4、5、6时
! N! B, Z, b4 |. ^
没有一个N能使M为非负整数
0 g7 w0 E1 ^' k' C/ }" w( E
所以I=31是素数。
% y. F3 T- ^' Y |5 D# G
数海聚珠网【程序体验】中的19、20、21号程序，就是利用合数公式得到的：
8 G1 P* ~( C# @( X% l" Z. t
1、精确判断素数计算素数个数，及寻找合数因数对
; b3 ~$ a9 a* t7 c) v3 T; U8 Z
2、精确计算哥猜数对
- u) w6 m4 Q3 d5 t+ e9 w3 f7 g
3、精确计算孪生素数对并计算孪生素数对个数
9 _. B' T) ^" C- E; [+ _) l
$ ?. g( @) `, _" |; z
*用19号程序：判断素数、合数及寻找合数的所有因数对，并且最后输出范围内合数、素数的个数。
# l$ n9 h. O6 r4 P, e) n
. O1 @6 i1 _/ D6 x1 H& n) x
下面寻找的是形如30*n+17且n在111111111-111111999之间的素数、合数及合数的所有因数对，并且最后输出范围内合数、素数的个数。
/ y. p' D- ^' G
输入：
3 w9 O' ]# z" i3 [7 q
用第二选项，E=17，h=111111111,，L=111111999，
# N- Q6 | ]2 E
先点击：并行参数开始，有数据出现，再点击：结果开始。
7 }- a6 T2 Q* k7 K# S
(T下面有X、Y值的就是合数，并且X、Y是T的所有因数对，没有X、Y出现的T是素数。最后输出的是在范围内，素数与合数的个数。由于较多，数据中间使用了省略号)
0 O/ s4 L/ G/ S; b, r7 U/ r
T=33333333347
1 {5 k& T& V. d5 K0 E/ E: e% s
T=33333333377
4 B1 p& i& M. P+ @: u }
T=33333333407
# ` b7 ~( U! ~ ? z6 U
X=3030303037
$ T- p- r8 d6 s. [! @
Y=11
1 }: V* V' Q- c
X=628930819
% D% \! T3 n1 u9 j
Y=53
4 g6 ]- D6 `1 h+ C" X e2 V
X=57175529
. y9 P& l( W) J+ G# ?6 \
Y=583
) a- r: P* O5 r5 a' Z
T=33333333437
- i0 E0 \: t9 P' p
X=254452927
( U/ e, V3 c1 Q% W
Y=131
' a" F9 B& O* ^
X=16347883
! G1 Z, i; \" z# p: T, J7 ]' J
Y=2039
) K7 v M; R: }) e4 j3 T; C9 L
X=267109
( a* s% P- O/ y- @6 M$ |+ I+ E
Y=124793
9 F0 D2 {% b, N" f/ j0 q' t
T=33333333467
9 B. ]" O" [8 O0 n7 T/ F% l
X=4761904781
2 D# X8 k' T6 D7 u5 O+ I; x) m
Y=7
9 B- d/ U( h* O/ p2 R! A" B
X=709219861
1 p8 f7 j4 O6 g! n% f6 h
Y=47
4 z- ^; k6 ?+ J' e; ~: D
X=311526481
# ]- [* Z& {& b
Y=107
9 p/ m- y# D2 S' t& O5 I. u& B; H$ n
X=138312587
8 u2 F$ b: N2 A) l+ d6 }
Y=241
+ i7 M. ^% N$ c$ w4 I8 u3 N! ~
X=101317123
) V) p' I( S: V0 B; d% U' r
Y=329
8 ~: @6 ~) U& ~9 E
X=44503783
8 r* [) { |0 m2 L
Y=749
Z5 j, p! O* o r, b) P
X=19758941
, j( f6 S6 b# M$ {
Y=1687
8 v5 n W8 U1 W
X=8483923
4 `! f* u. Q; j- q6 v! x6 s- W
Y=3929
3 d7 O& P. h0 q6 F$ k
X=6628223
3 v4 F6 x$ I1 B) T/ T; E% \
Y=5029
6 }# `! [# ^3 g) ?; F
X=2942821
. q& D7 {/ K! ~
Y=11327
# X3 z/ c1 j, q
X=1292641
7 I/ w. a1 p8 d7 I* S6 k
Y=25787
6 t/ W( a, h: i! I$ D+ Y
X=1211989
8 E) G$ Z! r. p: v: ~6 E5 y$ k" ?" @
Y=27503
* x/ R, j8 T9 M' j6 P/ }! K
X=946889
* S$ m( G; K9 l8 U# W7 N7 ~7 i
Y=35203
& J- Y! D/ H' Q
X=420403
0 j' k. k7 `9 b6 S; p7 ~& E
Y=79289
7 X+ a( L+ ~, X$ \9 P/ f( h$ f: w8 q
X=184663
# L# b' W8 {$ |7 W7 `: ^
Y=180509
2 C) m4 S7 v& I5 S# b. }: b5 L6 K
……
$ y$ p1 S( H; s# C7 Q3 V
T=33333335867
2 x/ h- L# i: N# ]
X=2564102759
2 X8 p( i0 \1 C" w3 @2 Y
Y=13
4 x0 P8 \/ P. z7 i
T=33333335897
! A" Q4 e, @9 c$ v v
X=2886253
$ z( m% F+ e* T4 ^: D3 g, @! L: w3 T Z
Y=11549
0 ~' T; D' {% V- m
T=33333335927
0 I2 `: K5 V5 u3 P Z6 @& `7 o S
X=900900971
$ ^ r* J! h2 B6 o* j
Y=37
0 d2 U' K9 U; F# ]2 M7 j8 n' b
X=1191881
b5 Z0 t* x( Q2 W, s+ [2 u/ @) y
Y=27967
( j& s5 r n# w% E0 b* W
X=1034779
) v1 |. q# v/ A, p
Y=32213
% b7 a* {" d% M3 P3 J
T=33333335957
1 k i6 y0 p i: m6 y( j% C
X=1754386103
2 i( c1 h: h% H5 z: F
Y=19
( K# y4 W, |) s8 w3 G4 ~! o# n
T=33333335987
! ~9 ~7 e5 N# A7 U0 y: G
X=4761905141
: B! X% ~& }- N2 R: A6 M2 Z0 i
Y=7
6 c& w9 ~% x5 P2 A3 o* w
X=680272163
2 ?* }; G: l5 b( M# H
Y=49
h( c- d( K/ i6 L2 `# ~ |
合计：89个
* Z% ]/ |; D% i. U+ [/ F8 C
素数：11个
1 I0 u4 h# U, E& i* Y- `
合数：78个
; ]+ P$ A+ j- v
]; a: g' _, E7 B1 O! B
若再选择第三种输出方式（输出的是所有素数及个数）
8 B" O0 R7 J2 v; P3 C/ ]$ ]
即：
/ t2 i0 N; ^; s' F, o/ f W1 a
T=33333333347
, U7 q( @/ a% ^; O/ P
T=33333333377
2 I ?& X* ?4 f! R
T=33333333647
2 J, `" H E3 r0 \1 i7 Z
T=33333333827
4 M- D0 s0 L0 a, o( G; [
T=33333333857
' O4 Y1 }2 A/ `* e; ~* K
T=33333334007
& U& P9 a" H0 U: ]+ w# s0 P
T=33333334487
( R; l" B3 p; i
T=33333334907
5 I# m! G% {; M e( X( \5 O5 I, e. Q
T=33333335027
# W! v7 t. b' ~: b: Z2 Z5 f: `2 N( _$ |
T=33333335177
" P. K) R( ]2 \0 o. b3 n
T=33333335657
4 \; k. Z9 u9 V" _3 C# R) x
素数：11个
1 U& q( [. |# G. a5 d% Q2 B# x( Y# R( X) F
6 J4 o) |9 I. U- V4 `7 E! O/ _
*使用20号程序:寻找哥德巴赫猜想数对
" x2 j* T) R5 n- y
4 [( [" ^8 T% s. v
用30n+11 与30n+23 组成的哥猜偶数30n+4(n最小为1)在1<n<111
+ k- T8 W: i0 y) x
输入：E1=11，E2=23，h=0，L=111
$ u9 K0 Y. V9 k& N0 E5 i+ Y
输出：
' Q# E0 i/ ?1 G! H
34有1对
- X+ e3 h' t, D' ~& v9 L: b5 e7 c
(11,23)
4 K1 v' u+ d, z; Q9 y9 |9 `
64有2对
& w# S5 h' ?3 t9 I
(11,53)
& ]" J! ~) \. q; }* C
(41,23)
. I2 S$ T3 o/ c* a
94有3对
# t5 l% p+ X5 Z4 o% d
(11,83)
/ e/ B* Y' z/ C8 n
(41,53)
]# o. Q( ~: q7 l; F& b
(71,23)
7 i( h; N8 f+ S/ d8 K
124有4对
% j O1 P6 y+ S
(11,113)
3 O' z$ z ]7 f1 O, F1 _/ m% o- M, X
(41,83)
- B) K, t7 ]; |. J* F
(71,53)
" Q' G& N) u6 |. U4 O# l, @
(101,23)
- @) q0 o7 o6 u% }3 N5 q# |
154有4对
: N& o' I) j" @+ Z
(41,113)
6 q- o$ j$ c7 M* E' J% g y$ k! W
(71,83)
* r" s; B% B; c0 U2 a$ { }
(101,53)
2 |7 P" h, C# }; e2 N/ x' m
(131,23)
% ?! _( N$ _* I9 R2 r
184有4对
( ~( A# ]" \% B }
(11,173)
& i) }' Z) _1 n' r. n
(71,113)
0 |* x4 O8 L* }7 s( b `
(101,83)
% D8 K; J: @# Z5 e6 [1 {0 J9 |
(131,53)
; _+ A5 z6 E* Z3 z' o; _
214有4对
) O; { y4 e3 T# ^5 T' _) U
(41,173)
- K7 O: n0 y8 g# l3 b. S7 ~: g0 V; H6 m
(101,113)
+ A3 A4 i% N6 Q3 w5 \3 Q$ E6 {# O* Q! |
(131,83)
* F) l( m# E# M
(191,23)
& t7 J6 ?+ `$ N2 a9 j; ^
……
/ Q! S, D2 r$ G
3324有24对
9 \# r) F$ q' M! K+ R
(73,3251)
# E6 Q6 l, ?2 f: u! y
(103,3221)
+ H9 K) r" o- _% q0 B
(283,3041)
1 h7 W: P1 K. W2 L ^5 @
(313,3011)
6 g& y. _' i0 L+ J) \
(463,2861)
' [. b& S' o8 s
(523,2801)
+ Y9 Z" l3 _7 A1 u
(613,2711)
" G: ^+ r+ b o
(733,2591)
& a Y5 Z! M8 L4 n% J* E
(883,2441)
8 q- m- N8 w2 j; B
(1213,2111)
: E$ r2 t$ P5 v1 \2 ?' K) }6 q! k
(1423,1901)
& [: M1 _: f) L3 y! |: K
(1453,1871)
) p- h# ~' T* X: H% z6 G# X
(1723,1601)
+ A; R! ]7 {- T- o/ @7 f$ u+ l+ S, ?
(1753,1571)
) x" _! }# n7 i& T2 `' H7 K- g8 ?# ^
(1873,1451)
1 ]8 x- Q8 q4 I
(2143,1181)
7 e: Q6 d+ @6 h G
(2293,1031)
9 m$ a4 f8 b0 e6 a, d
(2383,941)
' h5 N2 V: E, ?% T5 z* j" r6 ?
(2503,821)
; H5 d+ e) K; d1 I; M4 d( x |, f
(2683,641)
: `& ?' Y! \: n' N! H4 \
(2803,521)
& }& F9 s6 d N1 N& W, c
(2833,491)
; m6 q, k. L1 u* C9 f9 H+ k ^" |0 f
(3253,71)
+ o# E8 d9 }" E5 K+ _' F
(3313,11)
+ I% N3 u; D0 E" Z9 f( h
. G3 S; H7 u% K
*使用21号程序：寻找孪生素数对
/ B0 }7 B* K- X! O( X; r) T. p
e3 r2 }, J9 _5 V# C/ Z
用30n+11 与30n+13 组成的孪生素数n在111111111<n<111111999，
2 I, V) U, ?/ p: B/ s7 h
在程序中输入：E1=11，E2=13，h=111111111,，L=111111999
" c1 e$ p d; j
输出：
5 r5 ~9 g* L, ]
3333334391,3333334393
, W! R+ q D- L" {! @: a5 A2 t
3333335771,3333335773
! e0 B" m0 K% X3 a
3333336701,3333336703
" c y) s. P& H9 N$ \3 v/ z+ `
3333337661,3333337663
: [0 ~! N# O, o! P
3333338711,3333338713
/ R& H1 F/ w4 n! \* l4 V
3333339701,3333339703
/ I8 e9 y- Z% R4 u* P
3333340391,3333340393
' P- z! w+ [. o/ I2 ] \5 U
3333342401,3333342403
t% m) u3 P5 h4 R( c
3333342581,3333342583
" l. |. @. m% C$ ?& i$ T9 j- H
3333343421,3333343423
( _0 P: W/ D6 R3 V9 E/ G
3333345011,3333345013
) U) A; [' y; e- _$ g) r9 Z5 M
3333346061,3333346063
% e/ i K9 Q" P9 |' _
3333346571,3333346573
& N, t7 W' D1 {" _5 D
3333349751,3333349753
5 K# @0 Y5 o* X$ d" M4 v/ q
3333350201,3333350203
7 g$ O7 f; @6 s- e% E7 m
3333350261,3333350263
$ j' t7 v- }# M8 u$ ]+ t
3333350651,3333350653
. @. U- C1 K% _; ~8 }
3333351641,3333351643
' g/ U2 A& _3 H h$ d/ [5 u0 d: d- v
3333353531,3333353533
3 [% A' x- X$ G
3333355601,3333355603
0 ^" V+ Q# C& B% m
3333358211,3333358213
; ^6 y2 D- K- S1 P
3333358361,3333358363
* j0 \$ n! G! v# Y
3333358781,3333358783
; K" B* g4 @! u$ q, T* E0 i
3333359501,3333359503
3 H5 Z& t+ a& ?; g2 C
3333359591,3333359593
0 r/ j: L% l1 k7 \* J1 }
3333359831,3333359833
) E$ b) N# D: C {6 T
共有26对
3 h7 t$ L0 r7 s& l0 W7 ?
$ L& \- g6 P$ m3 w/ R
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5