数学建模社区-数学中国
标题:
合数公式 (判断素数或寻找合数因数对)
[打印本页]
作者:
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整除)，并且所有的合数都能联系在一起，形成一个等差数列网，这个网，呈上小下大的金字塔状，也可以说像树根状，如果把这个网从自然数列中抽出来，剩下的素数就没有规律了。相当于把一个形如树根的多串相连的珠子放进广口瓶中，然后用黄豆填满(填充的特点是下面豆子少上面的豆子多)，豆子与珠子各有自己的位置，根据所处位置看其是否被线串上，就知道是珠子还是豆子，如果把连在一起的多串珠子抽出来，剩下的豆子就看不出规律了，也就是豆子的使命是填充珠子没有占完的位置。自然数列中的项数就是合数与素数的位置，某一项只要不是合数就一定是素数。因此，要判断素数就要根据某数的特点，看是否存在于合数的等差数列网上，在网上的就是合数，不在网上的就是素数。
" X" b$ ^' P3 J5 p+ k, y
) w6 p( v+ A# Z5 ?$ s! @
下面是一个根据合数的网式规律而得到的最基本的合数公式(即：判断任意数)
Y: Q. V1 z/ Q7 O" k0 n, s
. R1 d5 A0 G5 h5 I: u' @
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是素数。
" R) p* j; P+ r( J6 p' \4 u0 ^
例1：I=27
% _ U9 c( x7 T9 O- ^0 q
因为I=27除以2的整数商为13
, ?& W. E, D; k5 d: Q
则：由合数公式M=(q-N)/(2*N+1)得：
$ W8 l- k4 L: }) j2 L! Y
M=(13-N)/(2*N+1)
. s0 o n( R, u
N的最大值为：I=27的平方根取整加1，即：5+1=6
0 N% Z! x5 I5 O2 i; O3 r
当N=1时M=(13-1)/(2*1+1)=4
! J7 H0 ]+ K( P0 U6 ?
则：(2*M+1)=(2*4+1)=9
c; P' l; a( r# O
(2*N+1)=(2*1+1)=3
7 \& W! P, M) `
即：(2*M+1)=9和(2*N+1)=3是I=27的一个因数对。
0 T& j* i6 v8 B6 }
同理：当N=2、3、4、5、6时
; j0 I/ y$ U) U) M7 u
只有当N=4时，才能得到非负整数M=1
+ S7 f3 j6 U9 T$ f, S- u
即：(2*M+1)=(2*1+1)=3
O* D" m6 R5 ~- r* Y
(2*N+1)=(2*4+1)=9
) r" [8 w: P0 s# }1 f
与前面的(2*M+1)=9和(2*N+1)=3正好相反
6 h1 F D6 t- a0 U" ^, B& \/ c
则：说明I=27只有一个因数对3*9(因数为1除外)
, g* j6 z/ D6 d. t9 A: x ~. I
例2：I=31
. o; e: W0 B2 z3 z$ W: M. r) c
因为I=31除以2的整数商为15
, s: U; } I) |
则：由合数公式M=(q-N)/(2*N+1)得：
& E8 W. B |/ H; Y1 E8 [7 u
M=(15-N)/(2*N+1)
: D& F' F+ i/ Z2 s$ z9 u
N的最大值为：I=31的平方根取整加1，即：5+1=6
' y, J+ m1 F4 _1 ?. |
当N=1、2、3、4、5、6时
, v4 K6 S+ V0 X; o0 n; G
没有一个N能使M为非负整数
. s4 p0 z1 S# g+ {0 d0 \
所以I=31是素数。
1 {5 r% I, p" Q) t: P* h6 M$ o
数海聚珠网【程序体验】中的19、20、21号程序，就是利用合数公式得到的：
1 _; Y6 M) U% I
1、精确判断素数计算素数个数，及寻找合数因数对
4 `# A0 C% J+ T$ b, ] c
2、精确计算哥猜数对
" w( t# H! O3 H0 V m+ F! t* ~+ U1 ?7 J
3、精确计算孪生素数对并计算孪生素数对个数
0 J9 @& ~2 R/ q) y3 k# X
6 ~# z$ u) k, C# B+ [
*用19号程序：判断素数、合数及寻找合数的所有因数对，并且最后输出范围内合数、素数的个数。
4 ]: G" R) c* m0 }
0 e6 O, u6 C, I( |
下面寻找的是形如30*n+17且n在111111111-111111999之间的素数、合数及合数的所有因数对，并且最后输出范围内合数、素数的个数。
6 N' a0 q1 ]+ \7 s* X/ V8 W4 ^' [! ~
输入：
2 V/ V( h) {6 d; G1 r, _' H
用第二选项，E=17，h=111111111,，L=111111999，
9 c: Z4 E1 S# C2 C
先点击：并行参数开始，有数据出现，再点击：结果开始。
: Y" g% v! R( H# V
(T下面有X、Y值的就是合数，并且X、Y是T的所有因数对，没有X、Y出现的T是素数。最后输出的是在范围内，素数与合数的个数。由于较多，数据中间使用了省略号)
" X& _; [! q, h W
T=33333333347
/ X* ?0 y) \$ [6 s. o3 z) X V+ M& {4 t
T=33333333377
# r( c% G& \: ~$ r
T=33333333407
, q6 m" J8 W6 v0 z6 Y
X=3030303037
' t; g' j3 ?2 V2 P ` A' z
Y=11
, C: Y- M% `! x6 e* G. j
X=628930819
% D2 J& W" {1 ]* s: V- ]
Y=53
m8 o6 x9 {- I3 H) u8 p# v
X=57175529
9 n) @" D0 c9 Q: c2 L
Y=583
# y7 Y9 u) ] y5 Q+ N; i! h. p
T=33333333437
8 J1 l9 M4 u' p, a7 Q
X=254452927
$ R$ l# n( @" A! W |
Y=131
5 B" r& N5 o* @) @8 ]% F9 }
X=16347883
& |! W& C: n' E0 `! j' s8 [
Y=2039
% d9 M& V! k2 G' W0 \' _$ @
X=267109
( e- [5 {2 b1 x+ |0 C: f
Y=124793
: _3 C: b7 o& \" r8 D1 s
T=33333333467
: c3 E: W! S8 w; p
X=4761904781
! |; x! e1 P1 S0 o
Y=7
$ Z8 a; I2 n) o$ Y
X=709219861
) _/ ^7 S0 ^! l) R. G8 h! W- h0 @1 A P
Y=47
/ @" f' M$ N! K
X=311526481
! y1 z6 B4 w3 _2 t# a* y1 \- M
Y=107
) R: Y, r" C3 E% q
X=138312587
( @( ~; a+ _# ~* x: I
Y=241
$ M: v% t! o" m+ S3 l+ S8 Q
X=101317123
3 w. u1 C: G. Z' G# k$ O3 n' a
Y=329
: c2 F# l! s+ V3 Y6 v4 ^! _* s
X=44503783
" w( d7 O& I" l+ d
Y=749
: d H2 C4 B$ G
X=19758941
/ `3 N, I1 b0 V m
Y=1687
* z! I/ r5 o) k
X=8483923
6 h6 o9 F. d4 y4 a, f. j1 K# f
Y=3929
; r0 j7 z, T$ \: R m2 [* }$ y
X=6628223
7 _0 d6 A! I, z3 k
Y=5029
4 z; A; q+ H5 |8 B6 ?. [+ S
X=2942821
% ~3 @3 e5 K$ Z0 M5 ]. P
Y=11327
2 S. Z4 Y! S4 [# N# ^: @" ^* Y
X=1292641
6 a0 N2 N) N$ s* ~% @7 A
Y=25787
9 f; D, ^2 Q+ c' }3 b
X=1211989
! x! ^& F! _$ s
Y=27503
" a" U3 g6 f" V; M: C+ Q
X=946889
( G1 h* ]4 s/ F
Y=35203
. u6 Q. |) K; P# i: E/ g
X=420403
+ n1 }' z. i9 K- b
Y=79289
) J) V; L/ u5 N: H& E' G1 a) u
X=184663
* p+ a; R( N" O* C8 D
Y=180509
- S% b- u) a& L& c' @ f4 n1 P
……
: @7 ~( N7 z! U5 w. F
T=33333335867
1 j' T6 y9 r6 A7 j9 ]- r
X=2564102759
7 X6 n: S [# m4 J% H* |) w
Y=13
( A+ d5 u; ?, ~1 V( s8 I# a
T=33333335897
0 @" U# J; K6 T7 R
X=2886253
' C- @, S2 l+ c& P; L8 K) C) ~% J
Y=11549
4 H" J3 S- q8 S* E" ~7 }& [
T=33333335927
/ o* D" [- C0 O6 Z- F
X=900900971
( p/ K* _, u# `1 j! ?, _8 v
Y=37
1 u6 O: N, h- h2 r; |7 J) T1 y
X=1191881
6 U. X8 L D: g: L( j
Y=27967
0 A' A0 h0 `4 t. L: r
X=1034779
& t" [- R: t6 e( K, [$ [$ |- \$ a
Y=32213
9 m7 z$ t" s- H& E( }
T=33333335957
; g& a2 o7 k6 O
X=1754386103
8 e! w1 r! F( o' T0 r$ a
Y=19
) Q0 Y# P5 Z: `7 |4 H
T=33333335987
; M0 M m9 R) w$ }7 |8 C; s2 F' c
X=4761905141
! u6 ^! L7 i" O5 c' D1 h X
Y=7
% C3 {7 I# n6 P$ |7 q9 b' n
X=680272163
# x/ y: l; t3 d2 [
Y=49
# I9 N! X0 W+ k, J1 Z( Q/ J
合计：89个
, B! W( P3 s2 B) \1 S. J& m. `5 w3 R
素数：11个
, k, E6 N2 c( N H9 Q& [
合数：78个
8 e5 I. g% m. i4 y3 R
+ s& I7 H; R+ q, s
若再选择第三种输出方式（输出的是所有素数及个数）
; b0 C6 e- Z8 M8 I
即：
9 Q E( [( W* m5 ]2 G. m
T=33333333347
4 J6 V' a# w& R) F$ l6 v
T=33333333377
+ I% K# j7 j o; B1 h3 S
T=33333333647
* r6 V6 n5 @+ i$ q. a+ Y v, s# y
T=33333333827
1 W3 t0 @! l' U
T=33333333857
: w. H/ D. f4 @2 E; k7 U1 r
T=33333334007
. R: c% ~ O( o0 G1 {1 w% F
T=33333334487
@: l, N$ s8 y, A S+ ]% B
T=33333334907
- e. Z4 h7 R6 n N
T=33333335027
2 S3 `& _5 A8 R0 ~# S
T=33333335177
% l3 U- ^( }; [+ R+ t* {% c6 U4 G
T=33333335657
) H% m; o5 ]9 X- n% W/ h* l
素数：11个
" Y k! S+ N& Y6 Y
% {: z$ `& M- p; B* N7 r
*使用20号程序:寻找哥德巴赫猜想数对
/ R" _$ |/ ?( F; w" v. s
$ m6 i8 Z4 _! @: x: m- I+ b/ G8 ]
用30n+11 与30n+23 组成的哥猜偶数30n+4(n最小为1)在1<n<111
# r+ ?2 ~; N& s$ W- [
输入：E1=11，E2=23，h=0，L=111
& K' G W0 J6 v9 F7 I
输出：
1 U( [: s3 m8 n4 e- U: E
34有1对
8 q1 O$ E* o, d+ m4 k. J5 K
(11,23)
; u4 V! F, k+ t$ S4 W
64有2对
7 r, l) s9 A5 X
(11,53)
7 C: O" R: C! ^/ n8 N+ H
(41,23)
3 l$ V* V7 K, A. z
94有3对
4 {! r% S1 u: O* x/ O D
(11,83)
v. ]4 F4 N$ D; C; [
(41,53)
+ h1 }/ {$ [; y6 G! t3 A# ^
(71,23)
3 h% E; M* G% h6 @9 p: |! j, S
124有4对
! X+ i3 y( q9 \% p9 H M
(11,113)
$ \( R, x6 P @, j0 m. h
(41,83)
# E' d C, C. j
(71,53)
* n- j$ H0 F$ ~& X2 J& D
(101,23)
7 E# `" F$ r7 X( U) F. z8 P# @1 L
154有4对
& ~8 o, k* a( C# e: w
(41,113)
: G) m& V$ W! B
(71,83)
0 Z1 d* [! G/ k+ t
(101,53)
& k L0 r D) M: W6 Q
(131,23)
0 M5 h/ i" N3 Z
184有4对
( e# W5 m/ X, J. F' z: ?
(11,173)
- u/ I, f+ d1 v% h( M! s
(71,113)
5 v; ^( j2 ]( P1 C0 q5 e
(101,83)
! {$ d0 N m; S* B. Z0 C- v9 i* J
(131,53)
* U( K5 R" O: q) ~4 R
214有4对
0 v. y9 C* i$ N
(41,173)
+ b% y/ X* K2 `& |
(101,113)
0 ~- g* O( H; O' f2 r
(131,83)
' E8 _% V. [6 J( U
(191,23)
3 [$ t) _. P; Z0 i7 e+ k
……
' X3 H0 m% \. y, G
3324有24对
% U' v" ?. M& o* }
(73,3251)
9 B' x3 Q8 v7 T5 g/ {' m! M% d
(103,3221)
2 k7 f p& o' k0 E# A/ ?# W4 `
(283,3041)
! f$ T$ y- S& \3 w( Q0 {
(313,3011)
, r9 k; R$ g: F3 b2 X' M4 ^+ S
(463,2861)
! n) M @( `, D% L* E
(523,2801)
7 Y: u. `7 ] s% A
(613,2711)
v7 G1 n/ s5 J
(733,2591)
7 n- j7 F9 `" Y( h4 c+ M' h% {
(883,2441)
! v# T: X+ q8 A/ ?2 E& g
(1213,2111)
+ B2 C( Z# _" ^* [. k9 M
(1423,1901)
/ {8 u2 R7 t R! D
(1453,1871)
0 u W9 i' X( p0 [
(1723,1601)
5 }: R( Z! B8 T7 i5 r" }- Y
(1753,1571)
$ i0 }; j* C" j: c5 T
(1873,1451)
0 H( X, k( W& ?& J: k1 _
(2143,1181)
. ~/ i' c8 N4 H: \0 Y4 E6 g$ H. O
(2293,1031)
- G( b' R# Q* ?' O
(2383,941)
6 X4 c+ R/ m! k8 p, C
(2503,821)
& U. F; ?/ v. q$ K& [) F
(2683,641)
0 N8 x( F6 `7 J1 Q. y9 f: g
(2803,521)
$ e9 Z' I" N% ` d/ f) w$ Q
(2833,491)
% ?/ V4 m0 I* e a
(3253,71)
9 A$ V. O8 t. F3 G$ h% a' f
(3313,11)
* A+ H8 ]" [/ _* `
! |+ f3 D$ u- r( ~: J9 y4 w
*使用21号程序：寻找孪生素数对
( i9 v O# q% W- y" d- N- W' p
, Q% t6 V0 | v6 v* I
用30n+11 与30n+13 组成的孪生素数n在111111111<n<111111999，
3 j6 ~; n2 n$ ^6 u
在程序中输入：E1=11，E2=13，h=111111111,，L=111111999
B$ P* ]' e0 Z: V2 Q4 L) C2 Y
输出：
; T% n' c+ a7 `0 ?
3333334391,3333334393
% H2 M8 x. M. T, G! _4 u: m- S
3333335771,3333335773
' {# u" h3 Y B1 S# J
3333336701,3333336703
% D- F; S6 g" r3 i/ L
3333337661,3333337663
) K, z' A7 S8 g
3333338711,3333338713
) V6 A0 l' v2 ?" {; X7 Z8 F
3333339701,3333339703
: F2 Z J6 `- t' y- o: S: z; Q' [
3333340391,3333340393
0 y( E% U5 `9 |+ N2 M: M6 u' w
3333342401,3333342403
$ t( Y& }$ x1 i: r; {& h: _ |- m
3333342581,3333342583
2 G8 ~3 j9 F' m: ~
3333343421,3333343423
; p4 e! `4 P% B* q# z+ v4 S
3333345011,3333345013
5 I: [- x" [1 L6 b, G3 J
3333346061,3333346063
: O. z, C$ ?7 x: V
3333346571,3333346573
) {8 P! e; O& B8 i% w- }8 i
3333349751,3333349753
0 D& ^! F# k/ y7 @( Q
3333350201,3333350203
0 z* }" H9 L; t# E/ D+ i% a6 o
3333350261,3333350263
- g# W' P8 d- z$ Y
3333350651,3333350653
# x& c1 z3 ^1 ^2 y9 D8 o
3333351641,3333351643
- @4 U) ]4 r& J9 }6 s1 Q, P1 v
3333353531,3333353533
5 B5 b; Q' K" v h
3333355601,3333355603
& }3 x& y2 s+ ~2 y% \% H
3333358211,3333358213
+ k* J& \) z" S6 D4 q
3333358361,3333358363
s8 M, L7 A, ?4 _2 T+ E
3333358781,3333358783
& y2 e) ?: y0 M. a- }8 c) {
3333359501,3333359503
( p8 u1 k m' q j
3333359591,3333359593
6 H! K. B+ F9 F+ O. K- v' P ^) C9 H: i- a
3333359831,3333359833
3 N# q2 Z% i; J( _. @
共有26对
7 a) a3 G) z N0 `! v2 O
6 o0 J7 U! U: C
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5