数学建模社区-数学中国
标题:
合数公式 (判断素数或寻找合数因数对)
[打印本页]
作者:
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 C
1 l5 A; ~# C* R; w u
下面是一个根据合数的网式规律而得到的最基本的合数公式(即：判断任意数)
! W# p% K( D; g' s; C; G* Z. h8 G
! p6 F( I9 [/ T( r; f7 f
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是素数。
' |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; G
M=(13-N)/(2*N+1)
4 {3 `: Z' g* ^6 T: r
N的最大值为：I=27的平方根取整加1，即：5+1=6
* H' g' J3 ~+ z( c+ }0 I$ X/ w; q
当N=1时M=(13-1)/(2*1+1)=4
0 A) M y6 l1 \, u) c' n g
则：(2*M+1)=(2*4+1)=9
7 x' R7 x. I* U
(2*N+1)=(2*1+1)=3
8 ^$ 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的整数商为15
7 H# H; E6 F" l2 w
则：由合数公式M=(q-N)/(2*N+1)得：
+ {& n1 x t1 d! W2 O( A* k
M=(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* i
2、精确计算哥猜数对
$ |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; H
T=33333333377
Z& M7 @ ]7 O+ {, j
T=33333333407
7 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 r
T=33333333437
& T" ~/ Q4 ~3 B$ s* B8 _
X=254452927
2 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=138312587
0 z& r' m$ ^, f+ U: ]4 D7 ~) C, o
Y=241
- q* F5 A* r j$ Z) c! l! N0 Z
X=101317123
0 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=35203
6 |# {3 b U- C" Z- Q, ^+ a& y
X=420403
7 \: [0 s! s. @1 ^+ L! V, H
Y=79289
) C7 k; I# i+ F. n! d. @7 A
X=184663
9 q+ Y. b5 A3 C8 }6 Z
Y=180509
3 I3 S# x& t$ X
……
" }2 h7 c9 T) N, {. m9 W
T=33333335867
+ [% g7 F0 K, ~/ a( v+ r
X=2564102759
z& X( Z: ?" z; y- F* [$ z. j
Y=13
. k6 A4 j9 z. J
T=33333335897
4 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=27967
9 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=19
2 I$ }6 H4 U% U: Q4 C, ?5 ]- Z, x4 {
T=33333335987
6 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 t
T=33333333347
5 f) o' J3 o; H( X1 u
T=33333333377
. J" P* H5 ~ D) \
T=33333333647
8 }) t/ U+ u( R( @6 K$ }* \
T=33333333827
* }# i0 e& y4 z5 C
T=33333333857
6 p/ y; {3 J# @9 E: S
T=33333334007
. p# V7 E* ] I3 @. {: w
T=33333334487
+ u+ v0 b7 g h
T=33333334907
) L* A5 _9 X% Z4 @6 c4 H2 v
T=33333335027
0 u+ ~" V7 q3 J0 O' W& r0 X
T=33333335177
3 g1 a9 v! q: m/ }. ?. o
T=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 |! @% `$ Q
34有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; `" E
184有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 ]: I
3324有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,3333335773
0 i& ?. `0 F- t
3333336701,3333336703
5 i, e$ ?. v7 O0 S. B, W
3333337661,3333337663
; t* `! d/ Y. C% |4 P- q) e
3333338711,3333338713
6 W6 h2 a( o. ^& c( _: Q2 \, u0 X
3333339701,3333339703
) O ], v. X- ]! C
3333340391,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 Y
3333343421,3333343423
: w0 G4 X9 f7 Q# z% _
3333345011,3333345013
6 z, t3 b1 p' K6 W- e5 E
3333346061,3333346063
! N! ^* e) ~6 a9 S
3333346571,3333346573
) d$ `1 M5 Y/ q" V" R) }8 S, q
3333349751,3333349753
0 z' J- z# T$ \% x" P( C# M. @
3333350201,3333350203
: P; ^$ a3 Y+ [' f$ Q& ~
3333350261,3333350263
' Y2 z' N. e- a* d+ l1 a
3333350651,3333350653
0 S$ @9 H5 n9 g' ~. d
3333351641,3333351643
* {' n" j( l1 W U; x
3333353531,3333353533
& H W+ }7 R j$ j7 J- D
3333355601,3333355603
# h/ M7 ]% w1 W
3333358211,3333358213
; f& ]& M6 D1 F) u
3333358361,3333358363
& j" ?6 a/ S, n9 L& W
3333358781,3333358783
" t4 R$ U8 Z) U$ n' ^' F% q9 r9 ^
3333359501,3333359503
- Z7 q ?$ e! i @, }/ K: c
3333359591,3333359593
3 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