■当前位置：首页 > VB 小程序 > VB查找素数：速度最快的代码

　 　 　 2. VB查找素数：速度最快的代码

'本人认为这是效率最高，速度最快的代码。如果有朋友另有高见，欢迎指教。
'程序要求：
'　1 查找 N 以内的所有素数，存入数组 Su()，计算查找总时间
'　2.将查找结果显示到列表框
'　3.查找和添加列表框的过程中有进度显示
''以下代码在 VB6 调试通过。
'　需要在窗体放置4个控件，不用设置控件任何属性：Command1，Command2，List1，Label1
Dim ctExit As Boolean, ctStop As Boolean
Dim ctCiFind As Long, ctCiAdd As Long

Private Sub Form_Load()
     Me.Caption = "查找 N 以内的所有素数"
    Label1.Caption = Me.Caption: Label1.AutoSize = True
    Command1.Caption = "查找": Command2.Caption = "取消"
End Sub

Private Sub Form_Resize()
   Dim S As Long
   On Error Resume Next
   S = Me.TextWidth("A")
   Command1.Move S, S, S * 8, S * 3
   Command2.Move S * 10, S, S * 8, S * 3
   Label1.Move S, Me.ScaleHeight - S * 4, Label1.Width, S * 4
   List1.Move 0, S * 5, Me.ScaleWidth, Label1.Top - S * 5
End Sub

Private Sub Form_Unload(Cancel As Integer)
    ctExit = True: ctStop = True '保证在查找未结束时能顺利结束程序
End Sub

Private Sub Command2_Click()
   ctStop = True '取消查找
End Sub

Private Sub Command1_Click()
   Static N As Long
   Dim Su() As Long, S As Long, Gen As Long, I As Long, J As Long
   Dim nStr As String, T As Single, Ci As Long
   
  '查找 N 以内的所有素数，存入数组 Su()，素数的总个数为 S
   If N < 2 Then N = 10000
   nStr = InputBox("请输入一个大于 1 的整数：", "查找素数", N)
   If nStr = "" Then Exit Sub
   N = Val(nStr)
   
   S = 0: ReDim Su(1)
   If N > 1 then S = 1: Su(1)=2 '■■根据冰麟轻武的建议，添加了本行

    ctStop = False: Command1.Enabled = False
   List1.Clear: Label1.Caption = "正在查找 " & N & " 以内的素数 ..."
   DoEvents
   
   T = Timer
   If ctCiFind < 10000 Then ctCiFind = 10000
   'For I = 2 To N
   For I = 3 To N Step 2 '■■根据冰麟轻武的建议，将上一行语句改成了本行
      Gen = Sqr(I)   '记忆 I 的平方根
      For J = 1 To S
         '进度显示
         Ci = Ci + 1
         If Ci > ctCiFind Then
            Ci = 0: DoEvents
            If ctStop Then GoTo Show1
            Label1.Caption = N & " 以内的素数：" & S & " 个，" & Format(I / N * 100, "0.0") & "%"
         End If
         '用 I 除以已经找到的素数■■交换下面两行代码，似乎能减少一次 Mod 运算
         If I Mod Su(J) = 0 Then GoTo NextI '能整除，不是素数，检查下一个
         If Su(J) > Gen Then Exit For       '检测到大于 I 的平方根就不用查了。删除此语句，结果一样，但速度慢得多
      Next
      S = S + 1: ReDim Preserve Su(S): Su(S) = I
NextI:
   Next
   I = N
   
'将找到的素数显示到列表框中
Show1:
   If ctExit Then Exit Sub
   
   T = Timer - T
   Ci = I / T * 0.3 '调整为查找过程中每 0.3 秒刷新一次进度
   If ctCiFind < Ci Then ctCiFind = Ci
   
   nStr = I & " 以内的素数共 " & S & " 个" & vbCrLf & "查找用时 " & Format(T, "0.00") & " 秒"
   Label1.Caption = "添加到到文本框 0%"
   ctStop = False
   
   If S > 65535 Then I = 65534 Else I = S
   List1.Visible = False
   If ctCiAdd < 1000 Then ctCiAdd = 1000
   T = Timer
   Ci = 0
   For J = 1 To I
      List1.AddItem Su(J)
      Ci = Ci + 1
      If Ci > ctCiAdd Then
         Ci = 0: DoEvents
         If ctStop Then Exit For
         Label1.Caption = "添加到到列表框 " & Format(J / S * 100, "0.0") & "%"
      End If
   Next
   T = Timer - T
   Ci = J / T * 0.3 '调整为添加过程中每 0.3 秒刷新一次进度
   If ctCiAdd < Ci Then ctCiAdd = Ci
   If List1.ListCount < S Then List1.AddItem "显示 " & J & "/" & S & " 个"
   Label1.Caption = nStr
   List1.Visible = True
   Command1.Enabled = True
End Sub

　　真心感谢“冰麟轻武”朋友的指教，这也不失为一种好的思路。
　　冰麟轻武说得非常好，使用 DoEvents 会使速度直线下降。
　　但是，如果不使用 DoEvents，当查找的数过大，所用时间较长，程序会进入假死状态，用户无法通过单击“取消”按钮终止查找。为了尽量减少 DoEvents 带来的速度减慢，我在程序中设置了变量 ctCiFind 用来控制 DoEvents 的使用次数，每执行 10000 次 Mod 运算后才执行一次 DoEvents 。

　　下面，在不使用 DoEvents 的情况下，我愿与冰麟轻武讨论一下代码速度快慢问题。
　　在此例中，程序执行 Mod 运算的次数越少，则效率越高，速度越快。

　　查找 1000 以内的素数两种方法的比较：
　　■我的方法：
　　当查到 997 是否是素数时，数组 Su() 中已存入 997 以下，共 167 个已找到的素数：
　　　　2，3，5，7，11，13，17，19，23，29，31，37，41，43，…,991
　　997 的平方根大约是 31.5（取整后是 32），只要除到比 32 大就可以了。
　　也就是，只需验证数组中前11个数（2，3，5，7，11，13，17，19，23，29，31），如果 997 除以这11个数的余数都不为0，则997肯定是素数，实际执行的 Mod 运算仅 11 次。

　　■冰麟轻武的方法：
　　首先，当执行“If N Mod 2 = 0 Then”会执行 1 次 Mod 运算。
　　在“For i = 3 To SqrN Step 2”中，SqrN 为 31.5，i分别为3，5，7，…,31，共执行 15 次 Mod 运算。
　　实际执行的 Mod 运算有 16 次。
　　另外，在冰麟轻武的代码中，有两个不足：
　　一、找到的素数会将 2 丢失，因此应在“If N Mod 2 = 0 Then”前面加上：
              If N = 2 Then Prime = True: Exit Function
　　二、“PrimeA = (i > SqrN)”疑为“Prime = i > SqrN”之误。

　　因此，我还是坚持认为，我的代码效率更高，速度更快。当然，在我的代码中，由于使用了数组，会占用内存，从而降低运行速度。但是，由于执行 Mod 运算的次数降到了最低，仍然会比不使用数组快一些。

　　■■再次感谢冰麟轻武，结合两种思路的优点，确实更快。我觉得，我们之间的这场讨论非常有意义。

　后记：本程序的改进见 查找素数-自制进度条-自制列表框 ，改进后的程序增加了自制的进度条、自制的列表框。

■当前位置：首页 > VB 小程序 > VB查找素数：速度最快的代码