论卢卡斯莱默素性测试的最高项

ysr

M521=6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151，素性测试结果：这是个素数4(1)
14(2)
194(3)
37634(4)
1416317954(5)
2005956546822746114(6)
4023861667741036022825635656102100994(7)
16191462721115671781777559070120513664958590125499158514329308740975788034(8)
262163465049278514526059369557563039213647877559524545911906005349555773831236935015956281848933426999307982418664943276943901608919396607297585154(9)
3485266917932376288990875234556574921883020918582159989616851051580995221114518058454754303289978723446136720263828339132923592090321129471424579224968542973(10)
444123373745504304939573734157073921708597420561221181603051505990623180251582707529238394955469281783437940704520956790021591340359481704683565385621096000(11)
6528971896985725779743891089687734681248808636038789276131082744718084087233021708956275240534357602732317122134365173340325179712463845933079590891660000589(12)
6623934232470573561330231933891111470483120711769595318280349228086412625644428033721391666570209411190334968600080841934854807082859961803358727418842197938(13)
6094697486964335281168055167078752729052776065103105339979510846658214809938710942146268763634801941350057478097580843979711961557595736908347534095238509950(14)
5963772770449912169901106087275724909384720273068987646424736715570392557774975649678783048707973688078170008545148518458766222746288082177494162928744280116(15)
3055071050067062355802649662030155736331913849704402224928928390419035361082386488352602099339708379230950503507164981175840877525023308207733452744553572773(16)
5339776747786148489049488751924832229201250099854890353211750611373125702310720287719449062054788960101425563525348582495584320053173734041024610723499740908(17)
780278826042834437674594872870758970001556881689320063494699600661570966398384873236133365021887702534983776547216296578284844117101728357611239825308761484(18)
结果对了，就是时间长，效率低
        一般都是第p-1项的余数为0，所以最高项就是p-1.

ysr

M157=2^157-1=182687704666362864775460604089535377456991567871<有48位>=852133201*60726444167<11位>*1654058017289*2134387368610417

ysr

Private Sub Command1_Click()
'验证和判断梅森素数的程序
'卢卡斯莱莫法
Dim A, B
A = Text1: B = Text2
ts = Timer
js = ksm2(Val(B))
js3 = MPC(Trim(js), 1)
s = 4
s1 = 1
Do While s1 <= Val(B - 1)
s2 = s2 & s & "  " & s1 & vbCrLf
If Len(s) = 1 Then
If Val(s) = 0 Then
s5 = "这是个素数"
Else
s2 = s2
End If
End If

s = MPC(zhengchuqyushu(MCC4(MbC(Trim(s), Trim(s)), Trim(js3))), 2)

s1 = s1 + 1
Loop
s3 = Len(js3)
If s5 = "这是个素数" Then
Text3 = "有" & s3 & "位，用时" & Timer - ts & "秒  " & js3 & vbCrLf & s5
Else
Text3 = "有" & s3 & "位，用时" & Timer - ts & "秒  " & js3 & vbCrLf & s2
End If

End Sub

Private Sub Command2_Click()
Text1 = ""
Text2 = ""
Text3 = ""

End Sub

ysr

Public Function MCC4(D1 As String, D2 As String) As String ';大整数的快速除法
Dim ss
ss = MBJC(D1, D2)
If ss = -1 Then
MCC4 = "0" & "/" & D1
  Else
  If ss = 0 Then
   MCC4 = 1
   Else
   If Len(D1) = Len(D2) Then
Do While MBJC(D1, D2) >= 0
S1 = S1 + 1
D1 = MPC(D1, D2)
Loop
If D1 = 0 Then
MCC4 = S1
Else
    MCC4 = S1 & "/" & D1
End If
    Else
    If Len(D2) < 9 Then
     MCC4 = MCC(D1, D2)
     Else
    Dim X, Y ';定义分段长度
   
    X = Len(D1) \ 4: Y = Len(D2) \ 4
    If Len(D1) > 4 * X Then
    X = X + 1
    D1 = String(4 * X - Len(D1), "0") & D1
    ElseIf Len(D2) > 4 * Y Then
    Y = Y + 1
    D2 = String(4 * Y - Len(D2), "0") & D2
    Else
    D1 = String(4 * X - Len(D1), "0") & D1
    D2 = String(4 * Y - Len(D2), "0") & D2
    End If
  X = Len(D1) \ 4: Y = Len(D2) \ 4
Dim JW, jcc, jss, jcs

  Dim A() As String, B() As String
  
  ReDim A(1 To X)
  ReDim B(1 To Y)
  For I = 1 To X
  A(I) = Mid(D1, I * 4 - 3, 4)
  Next
  For J = 1 To Y
  B(J) = Mid(D2, J * 4 - 3, 4)
  jws = jws & A(J)
  Next
If Len(qqdl(Trim(jws))) <= Len(qqdl(D2)) Then
  jcc = Val(Left(qqdl(A(1) & A(2)), 2)) \ Val(Left(qqdl(B(1) & B(2)), 2))
  Else
  jcc = Val(Left(qqdl(A(1) & A(2)), 2 + Len(qqdl(Trim(jws))) - Len(qqdl(D2)))) \ Val(Left(qqdl(B(1) & B(2)), 2))
  End If

  jss = MbC(Trim(jcc), D2)
  
   
      Do While MBJC(Trim(jws), Trim(jss)) = -1
      jcc = jcc - 1
      jss = MbC(Trim(jcc), D2)
      Loop
  JW = MPC(Trim(jws), Trim(jss))
  
    z = X - Y
   
    Dim c() As String
    ReDim c(1 To z)
    For s = 1 To z
     If MBJC(JW & A(s + Y), D2) = -1 Then
       c(s) = "0000"
       Else
       If Len(qqdl(JW & A(s + Y))) = Len(qqdl(D2)) Then
  jwc = Val(Left(qqdl(JW & A(s + Y)), 4)) \ Val(Left(qqdl(B(1) & B(2)), 4))
  Else
  If Len(qqdl(JW & A(s + Y))) <= Len(qqdl(D2)) Then
  jwc = Val(Left(qqdl(JW & A(s + Y)), 4)) \ Val(Left(qqdl(B(1) & B(2)), 4))
  Else
  jwc = Val(Left(qqdl(JW & A(s + Y)), 4 + Len(qqdl(JW & A(s + Y))) - Len(qqdl(D2)))) / Val(Left(qqdl(B(1) & B(2)), 4))
  jwc = Format(Val(jwc), "0.000000")
  If InStr(jwc, ".") = 0 Then
  jwc = jwc
  Else
  jwc = Left(jwc, InStr(jwc, ".") - 1)
  End If
  End If
  End If
     c(s) = jwc
         End If
       jsw = MbC(Trim(c(s)), Trim(D2))
       Do While MBJC(JW & A(s + Y), Trim(jsw)) = -1
      c(s) = c(s) - 1
      jsw = MbC(Trim(c(s)), D2)
      Loop
     JW = MPC(JW & A(s + Y), MbC(Val(c(s)), D2))
     Do While MBJC(Trim(JW), Trim(D2)) >= 0
     jwc1 = jwc1 + 1
     JW = MPC(Trim(JW), Trim(D2))
     Loop
     c(s) = Val(c(s) + jwc1)
    c(s) = Right(100000000 + Val(c(s)), 4)
     
    jcc = jcc & c(s)
    Next s
    If JW = 0 Then
    MCC4 = jcc
    Else
    MCC4 = jcc & "/" & JW
    End If
   
  For I = 1 To Len(MCC4)
    If Not Mid(MCC4, I, 1) = "0" Then
        Exit For
    End If
Next
strTmp = Mid(MCC4, I)
  If Len(strTmp) = 0 Then
  MCC4 = "0"
  Else
MCC4 = strTmp
End If
   
    End If
   
  End If
End If
End If
End Function

ysr

例：2^89-1

有27位，用时0.3007813秒  618970019642690137449562111
这是个素数
4  1
14  2
194  3
37634  4
1416317954  5
2005956546822746114  6
598028640278675810224740676  7
480114390397887436345871973  8
256286478379806120980640370  9
503856043838036255396725647  10
511097357768708595775143636  11
168909432968702305299180947  12
606396047570974655444193748  13
384259961875522880452984663  14
400988785643977730394319793  15
451946598706049129545781082  16
519056096255902175211532475  17
121085530627461043345077875  18
71186560963388750687096830  19
36000517785442762303479300  20
523566428507141573725342798  21
424152844029608571078391252  22
451425083283677785701240528  23
471604984152655775544654653  24
149504332299367259583502770  25
2661688372237296008669225  26
14651690105229857026329789  27
118366775657027743761992789  28
78447114542527441733697497  29
414825479001522844830957808  30
140234396746501638380162556  31
524724811145776165191705380  32
454239684978083396425387798  33
443190129321733552688414291  34
193246662398964773806577169  35
90276720159245463714588945  36
325532186394213993941115709  37
184428441183694588040637933  38
20227257621080411005543513  39
492178310326013754654519350  40
98383234722633752804518339  41
422539297718609229503207527  42
239699647065516513819077229  43
451540821309242236737612159  44
386616582127510358048893037  45
111015693969297793247714068  46
526524283201479916042588129  47
64862389039487459674212268  48
222734658450663017797297098  49
527979459006852476995019463  50
597546382855243971575029724  51
432108610907467792010713113  52
267528776084781116062417378  53
539136831481300028111816217  54
451247597566784449829767505  55
437168526145243171726687748  56
598500912756632689317072800  57
524692914241987400050525363  58
332189870719179258780519572  59
412661427218334854756142421  60
321992305401224654215082066  61
435970785565830723987708026  62
381742226819095467298228805  63
170103210134157444573479299  64
529650761375006727395831727  65
588636842041150882786657416  66
532115895320758084925029926  67
501541201809618824302560067  68
339657887315362077441027847  69
99498791857820493810407653  70
267353229805674813483082782  71
153775828163901691352640258  72
645734370591155030147282  73
239072406272077525999142496  74
386211355975098724888629576  75
589820547708179745896185533  76
426471425099610829450724237  77
14792991384462166970694984  78
574596879853011245099388238  79
269783273665984523074966550  80
98263195276941167273641778  81
288575740080467405879843347  82
592120439037291200756916902  83
248352176262993969312953851  84
496815502059771466001738628  85
309566686160249986820679689  86
618970019642654953077473279  87
0  88