数学建模社区-数学中国
标题:
合数公式 (判断素数或寻找合数因数对)
[打印本页]
作者:
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整除),并且所有的合数都能联系在一起,形成一个等差数列网,这个网,呈上小下大的金字塔状,也可以说像树根状,如果把这个网从自然数列中抽出来,剩下的素数就没有规律了。相当于把一个形如树根的多串相连的珠子放进广口瓶中,然后用黄豆填满(填充的特点是下面豆子少上面的豆子多),豆子与珠子各有自己的位置,根据所处位置看其是否被线串上,就知道是珠子还是豆子,如果把连在一起的多串珠子抽出来,剩下的豆子就看不出规律了,也就是豆子的使命是填充珠子没有占完的位置。自然数列中的项数就是合数与素数的位置,某一项只要不是合数就一定是素数。因此,要判断素数就要根据某数的特点,看是否存在于合数的等差数列网上,在网上的就是合数,不在网上的就是素数。
6 l6 A) p2 |( M& ~$ F W
% A3 M9 a8 [* C& t) n
下面是一个根据合数的网式规律而得到的最基本的合数公式(即:判断任意数)
0 z3 p7 j( Z2 R" R5 S5 [
5 _+ n/ A7 n; f! m# z$ `: X
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是素数。
, X& U4 A+ u$ Q! ~
例1:I=27
3 L3 L0 w/ u6 t
因为I=27除以2的整数商为13
, ]" r! G) @3 Q, T& P
则:由合数公式M=(q-N)/(2*N+1)得:
, T0 w; f0 @* |7 G6 W& l3 w8 K
M=(13-N)/(2*N+1)
4 I" M0 v9 _; V
N的最大值为:I=27的平方根取整加1,即:5+1=6
' d2 M7 a) f: A" A* ?9 B+ C, T
当N=1时M=(13-1)/(2*1+1)=4
n/ V8 |# b6 j2 D) `$ A
则:(2*M+1)=(2*4+1)=9
% d" W: j% \8 b, r/ r5 W3 ]# o. j
(2*N+1)=(2*1+1)=3
5 D# c; B7 e4 t+ g2 G/ ^ a% H2 U
即:(2*M+1)=9和(2*N+1)=3是I=27的一个因数对。
! H$ T9 _3 C" @: s$ o. q+ s
同理:当N=2、3、4、5、6时
! V& {2 F/ L& U" }
只有当N=4时,才能得到非负整数M=1
% Z9 }3 S. m j- ~6 ^( M1 @; x# N
即:(2*M+1)=(2*1+1)=3
9 z7 Z0 G# u4 R% g* b
(2*N+1)=(2*4+1)=9
& F% y* E A, ]/ ?0 D# E2 I
与前面的(2*M+1)=9和(2*N+1)=3正好相反
# V, S2 v; N5 ?6 _& q( ^+ w
则:说明I=27只有一个因数对3*9(因数为1除外)
! H; f7 u& L H' \
例2:I=31
3 m+ A$ a; ?" B0 n8 E! L
因为I=31除以2的整数商为15
: E6 C) O4 |3 D, o" f+ k) Y: j$ r
则:由合数公式M=(q-N)/(2*N+1)得:
: ], P8 M3 X4 e0 K# M! i6 ]$ R
M=(15-N)/(2*N+1)
% G+ w+ M3 c! D! B$ F
N的最大值为:I=31的平方根取整加1,即:5+1=6
) S1 h' t/ F* s+ z
当N=1、2、3、4、5、6时
h/ T8 k. b6 Y7 X: N
没有一个N能使M为非负整数
5 I5 P2 J: }0 \
所以I=31是素数。
; l3 D- T% ~( w; b( ^' R
数海聚珠网【程序体验】中的19、20、21号程序,就是利用合数公式得到的:
7 S! H$ d7 I5 F& d" y
1、精确判断素数计算素数个数,及寻找合数因数对
' b+ }$ E3 R9 o' s
2、精确计算哥猜数对
4 V7 \& U: a5 X; [( b. Q
3、精确计算孪生素数对并计算孪生素数对个数
( z& N# c7 W9 m" c* J6 V+ Y ^5 Q
* l7 ]: K& E6 U' T
*用19号程序:判断素数、合数及寻找合数的所有因数对,并且最后输出范围内合数、素数的个数。
, a# p6 ?$ L: B' D0 i5 e
$ t5 c) r; E; c3 a! O4 n
下面寻找的是形如30*n+17且n在111111111-111111999之间的素数、合数及合数的所有因数对,并且最后输出范围内合数、素数的个数。
% R5 Q5 y: D4 y
输入:
* E$ n* \8 @- T
用第二选项,E=17,h=111111111,,L=111111999,
. v" a S2 ]6 ?" Y" `% `
先点击:并行参数开始,有数据出现,再点击:结果开始。
1 B3 A; p0 Z8 N, k+ v
(T下面有X、Y值的就是合数,并且X、Y是T的所有因数对,没有X、Y出现的T是素数。最后输出的是在范围内,素数与合数的个数。由于较多,数据中间使用了省略号)
) u) G3 o, d R3 D& E, U0 f3 ^
T=33333333347
. H* q! V! m5 M' J
T=33333333377
" W9 \0 H; C: S7 s& h) ?
T=33333333407
: v4 F( P# L7 Z; U# l! N
X=3030303037
7 |8 I% e! m7 j7 F) ^2 T
Y=11
' c# y4 `& o1 `; y5 g
X=628930819
1 P) s) x6 q, Q+ w9 F3 m% n9 |
Y=53
. P& D6 H3 Y6 f$ k, U- \3 h
X=57175529
. s! ]" l9 h- u( `3 _) `( G9 p
Y=583
0 u5 a r& s" q& o
T=33333333437
: v0 `9 H2 \% \9 H0 A# b% K& L2 [; h
X=254452927
5 \# T$ H" Q, b) r% n
Y=131
3 |6 z$ z" Z# `0 }3 G: M8 k B, B
X=16347883
, a1 i- t) G+ A6 V7 ?
Y=2039
9 o S$ a5 X3 v& T! k/ k N F
X=267109
' Z2 H- a3 z. q: a) {* v/ E
Y=124793
6 j: }1 F* h. A; A+ ]* a; `
T=33333333467
8 A7 [$ O, K3 M C9 x( Q1 o
X=4761904781
) n, h% Q. g0 n4 C$ u- x+ y
Y=7
$ d9 W( N% |6 }1 x
X=709219861
$ Y) E! d3 V2 H8 _! V
Y=47
5 I4 p7 a0 a3 }1 E
X=311526481
, f, O' b6 U: ]1 b% g& k4 H& B
Y=107
: O5 C; a$ O; H3 M2 F, C
X=138312587
* @( p, J' r7 U0 L- G. v
Y=241
3 i5 l3 m5 v$ a- V9 ^( y
X=101317123
; Y( z6 e% ?) S: S
Y=329
3 L; X- \# S. `
X=44503783
2 `" K/ _9 \- p# N4 ?
Y=749
2 ?. I D6 ^- F* n" X( e
X=19758941
6 w9 l% t+ e+ k) U0 u6 I4 d/ h9 B
Y=1687
3 _5 Y/ Y- U; G+ \
X=8483923
3 J- k8 e; m/ ~# `" Y2 W" q) G+ \0 N
Y=3929
B' j, p. q. U3 O7 G w2 L: a
X=6628223
" r& z+ r8 R' D8 h4 _! E
Y=5029
" x" }: Q: v# z/ y
X=2942821
. m! @7 R. g6 V$ l, r4 e ~- k
Y=11327
0 A. _6 w4 ]- }$ u1 w
X=1292641
3 b4 i0 O. W8 q: d: P) R$ D1 t
Y=25787
9 S: C/ u B c u5 D! Z( x# y* I+ y2 r
X=1211989
4 A2 w! U3 Z4 F. M1 u/ b$ r
Y=27503
2 k- h) Z/ y d% h0 j
X=946889
3 }* M% e4 H0 Q6 S
Y=35203
2 @' T4 B& P1 v$ {- f+ J3 N
X=420403
/ `5 j/ L0 h) A4 G3 y
Y=79289
6 y5 Y7 p2 W6 [% y
X=184663
2 |- b' Y' ]2 k$ A; O( b' Q
Y=180509
/ x( \* s1 `" g
……
. D* P" z+ d/ n! m
T=33333335867
6 e m8 f1 A( A) V1 m
X=2564102759
: K" ~& _/ L& B5 M5 Y( K
Y=13
' J: Z, B, J- R% w
T=33333335897
7 x7 ?& S. d; C2 i! p2 o& E
X=2886253
6 d k/ J3 ?) P6 }" W- ]0 i
Y=11549
" ^6 O9 h5 a0 S& {9 X
T=33333335927
" e8 e. @8 {$ C' o! M
X=900900971
! D2 m* q, x& }& p+ y. M
Y=37
' N$ A5 ]. j' ^1 S* M
X=1191881
8 Y# R e) _0 s7 ~
Y=27967
# m6 K; a; r4 h; d' L+ g7 k8 q3 ~
X=1034779
) `6 x. d# {, b
Y=32213
" z1 z4 v1 O G6 P' m
T=33333335957
0 t! ^3 U. m6 D
X=1754386103
, K D) _5 S2 r! i9 L. }
Y=19
7 e4 r. G4 k' m, T7 ]
T=33333335987
7 H9 P+ F2 ?/ F, H: G. ?/ q
X=4761905141
0 b. A$ d: |% G* ~' L. O! Z' f
Y=7
7 c) G; n8 i+ [! }8 |2 J2 |3 S0 g
X=680272163
0 x& N! T* e6 ~7 X
Y=49
: A3 ?: k+ Y4 B! v# `
合计:89个
4 M, h; g' ~9 ^6 F9 l
素数:11个
. A% q; ?6 q) m8 `3 S" J2 Z
合数:78个
% s5 s. H7 L. I
' M$ U \& E3 o, r5 t& j* s! V. O
若再选择第三种输出方式(输出的是所有素数及个数)
- ]7 U7 D$ g+ a; W7 L- O0 B
即:
1 P* @$ i) N1 y) P- I9 @
T=33333333347
, o$ S; B1 W2 B c& I) f* a
T=33333333377
# [! H5 ^" V0 o3 p- J
T=33333333647
' R6 q& k5 ^8 Q6 u+ L3 q# y
T=33333333827
5 W6 t, I0 H! ^$ A
T=33333333857
9 }; |! t3 @/ z6 k. C' K
T=33333334007
; @7 s( x4 [; N& i. @1 E) C7 \
T=33333334487
* h* x# Z8 F+ R. f, x8 _+ j
T=33333334907
. @2 N( a- z! Q5 C5 m
T=33333335027
$ k2 Q; `6 ?; U9 m
T=33333335177
4 D r/ W1 u3 I5 u0 S
T=33333335657
5 ~9 O! ]0 l" K, c9 b1 Q
素数:11个
# w7 f& F7 g: `% b, j0 B/ `
* ^: n# P; h( e1 n( t' _; K
*使用20号程序:寻找哥德巴赫猜想数对
/ @7 u: d: E9 J! v( C) E5 J0 I
z% U7 f. X$ h2 ^6 I+ w; v
用30n+11 与30n+23 组成的哥猜偶数30n+4(n最小为1)在1<n<111
: U9 w g5 ^* w" Y
输入:E1=11,E2=23,h=0,L=111
4 d+ i: P n' @+ z |( L! S
输出:
+ O" T1 Y7 E. p' b" m3 C
34有1对
" V, k' Q7 S" w! j
(11,23)
& m1 I) ?& X5 d) Q( [
64有2对
f0 Y8 n, ]3 |: H9 ~% i
(11,53)
! l+ r# ^3 w6 g( N) {
(41,23)
( e* f" }0 ~0 g2 O5 j1 a" e ]
94有3对
1 R0 d6 K- V2 u! V5 R
(11,83)
i6 X8 i* |( {7 B- Q* b
(41,53)
; H- H. @8 N) Z. x
(71,23)
9 _1 D( I5 a7 |' D
124有4对
4 a C9 [0 A6 b. \( @( U U
(11,113)
7 K) x' k$ B# G$ F( {
(41,83)
& v# R: H( Z6 Y/ o8 N4 [! E2 U- |
(71,53)
( J6 {9 g: W/ j( F# N$ U" A; r
(101,23)
" o- K E1 y* x$ \( y
154有4对
3 {/ P1 M4 }! b* i- {
(41,113)
+ S) \. m, U& X2 U) k
(71,83)
9 Y6 E' K7 n* y& z
(101,53)
( d$ w0 ?- y$ k1 P0 K2 H7 `
(131,23)
- {" Z; E+ `7 `. b
184有4对
6 S6 d$ \. `2 N9 d B8 ]% O
(11,173)
& V5 o6 ^" M( ^% w% p G
(71,113)
1 s7 J7 p6 b3 e" R
(101,83)
; d! k& I! ?. F0 H: q
(131,53)
: X# n5 a1 A. s- f X
214有4对
+ _7 y, R( V1 N$ G
(41,173)
! x) X. t0 A' O9 w$ A. B. g! \
(101,113)
* n6 V; j ~: ]
(131,83)
" w9 m8 w) m; x/ N% P1 z
(191,23)
% m" N! E8 A/ U
……
2 }; [8 V$ W+ T v! B
3324有24对
# G% h9 B3 H; w K6 j5 r
(73,3251)
6 Z# I3 g! T1 }. q6 W) M+ @0 K
(103,3221)
( |# L. Q' \" C4 S9 f& |. ^5 r
(283,3041)
' R/ O" f( W7 l4 x/ C# }/ i
(313,3011)
' i( p6 G% _5 l0 K0 V, I7 E
(463,2861)
0 k& k' u& l0 R( |1 |3 w" B) U
(523,2801)
. g, [6 K# ?6 s5 k) O+ @
(613,2711)
; W$ E. ]+ ^2 x) [: |
(733,2591)
" Q5 A$ a6 X" v& W. G
(883,2441)
& U' H1 q4 L% [: @$ ^, {
(1213,2111)
- U1 R& ~# d+ [5 n
(1423,1901)
2 d* N5 c) ^9 Q7 s ~
(1453,1871)
4 z, p- S1 o2 w# e, u
(1723,1601)
( a' H0 c! p5 X/ G; S, j+ O
(1753,1571)
; \$ u# h) n- e2 k- i; W
(1873,1451)
( S! {4 p+ n7 @
(2143,1181)
# S4 g* C: X& S2 P
(2293,1031)
* F4 g0 C4 k. o/ @9 c
(2383,941)
( k( c* B* i a' `+ C# s
(2503,821)
& R2 ?2 M, V4 m
(2683,641)
; N4 R% x! U, I# \0 q0 C! Z! \; P
(2803,521)
% E; R- y. ]" d2 o' A
(2833,491)
* j0 a, J8 P3 U
(3253,71)
2 Z2 v" y* I3 G, y" Z, V
(3313,11)
1 o* S/ L* H& C: p
% }) @4 L9 g" A" q& E l
*使用21号程序:寻找孪生素数对
0 M" T, x9 _; B0 b
7 H H6 [; V- \. J; L
用30n+11 与30n+13 组成的孪生素数n在111111111<n<111111999,
& t& h0 k3 k s1 m* A6 ` K' d
在程序中输入:E1=11,E2=13,h=111111111,,L=111111999
& x- Q: F% n+ o
输出:
' e" c" C; u( j3 h, V- Y9 D
3333334391,3333334393
3 k2 ` g1 b6 A( E
3333335771,3333335773
1 H+ V: g* Q0 I7 _
3333336701,3333336703
* E/ L1 Z3 u0 z
3333337661,3333337663
1 b6 @7 `. C) W8 ]
3333338711,3333338713
; E, r; w2 S9 I4 M
3333339701,3333339703
h7 h% n: S8 C* ~, Q% C/ B
3333340391,3333340393
8 S! ]1 S9 R% a) Y- i ?
3333342401,3333342403
2 D2 h9 v$ `3 k$ c) \
3333342581,3333342583
p! U" I+ I" v: R/ x0 u) a& p3 H
3333343421,3333343423
# a0 L4 G* T% A0 U' a+ K0 v9 J, Q
3333345011,3333345013
# q' b W8 N& Y" J9 T' Z4 {7 A; A0 J
3333346061,3333346063
& w5 @' |9 L6 A9 |" _+ Y
3333346571,3333346573
& a r% A( d% S: o4 ? Y9 e
3333349751,3333349753
' T3 D$ Q7 w3 A* L D+ Q9 W
3333350201,3333350203
- Q& s, y/ a$ W( g
3333350261,3333350263
8 \. @2 B& Y1 U. Y6 ~, V/ e" C
3333350651,3333350653
* Y# O1 q1 o' A
3333351641,3333351643
; K' r9 r+ p; h3 p
3333353531,3333353533
$ i6 K8 L* r( E4 G# b: ?, U
3333355601,3333355603
: c: A! n6 F5 x# F! B
3333358211,3333358213
7 J# z- W) M$ a9 d7 u8 E
3333358361,3333358363
) {0 [/ U) q& Z6 N* y
3333358781,3333358783
" J1 L1 n9 q3 G$ J7 i+ N% |# i
3333359501,3333359503
; O# K# ~* ^2 s) K
3333359591,3333359593
c1 L) D2 L$ J7 f8 h$ F
3333359831,3333359833
, v' I& n3 w# j9 e
共有26对
5 y* b' E. J% s3 P' c
p9 V3 ~1 q- [* o
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5