none
關於VB6質數判斷.... RRS feed

  • 問題

  • hi~ 大家好^^

    小弟最近作題目遇到了一個質數判斷的問題,而小弟在網路上找了一下 找到利用(2^n)-1判斷質數的公式,可是在程式上跑時能判斷比較小的數,較大的數字就會溢位了....

    懇請大大建議^^

    以下是小弟的程式碼

    ps.題目:計算2到N的質數和,及最接近N的質數、2到N共有

                   幾個質數

    Dim i, N, om, cnum, winum As Integer, STN As String, NYN As Boolean, lns, j, S, nsum As Long

    'cnum 為質數個數 lns為餘數 nsum 為質數和 winum 為最接近N之質數

    Private Sub Command1_Click()

    STN = Text1.Text

    NYN = IsNumeric(STN)

        If NYN = False Or Val(STN) > 32767 Or Val(STN) < 2 Then


        MsgBox "N超過32767或小於2,請重新輸入", vbOKOnly, "警告"

        Text1.Text = ""

        Else

        N = Val(STN)

        For i = 2 To N

            If i > 2 Then
       
                om = i - 1
       
            Else

                om = i

            End If

     
            S = (2 ^ i) - 1

            For j = 2 To om

                lns = S Mod j
           
                If S = 2 Then
                
                    lns = 1
                
                    Exit For

                ElseIf lns = 0 Then
               
                    Exit For

                End If
           
            Next j
               
    If lns <> 0 Then

        cnum = cnum + 1

        nsum = nsum + i

        winum = j

    End If

    Next i

    End If

    Text2(0).Text = cnum

    Text2(1).Text = nsum

    Text2(2).Text = winum

    End Sub

    Private Sub Form_Load()

    With Label1
         .Caption = "input N=? (2<=N<=32767)"

         .Font = "Times New Roman"

         .FontSize = 12

    End With
         Label2.Caption = "2到N之所有質數個數"

         Label3.Caption = "2到N之所有質數和"

         Label4.Caption = "最接近N之質數"

         Text1.Text = ""

         Command1.Caption = "計算"

    For i = 0 To 2

         Text2(i).Text = ""
     
    Next

         Me.Caption = "質數尋找及計算"


    End Sub

    2006年11月21日 上午 02:02

解答

  • 你的公式有問題。

    求質數的上限也是 Int(Sqr(n)),Int(Sqr(7)) = 2 只要檢查 2 能否整除即可。

    而要整除的對象,是質數,不是 2 ~ 6 ,而是小於等於 Int(Sqr(n)) 的質數。

    所以演算過程要動態建立 2 ~ Int(sqr(n)) 的質數,另外你的推論也有問題:

    ex:n=3(被判斷的數)

    (2^3-1)=7

    7不能被6~2這個範圍的數整除

    所以3為質數!!

    3 可能被大於 3 的整數整除?數學上也不通吧?那 n = 4時,2^4 - 1 = 15

    15 能被 3, 5 整除,所以 3,5 不是質數?或是 3, 5 是質數?

    邏輯整個是錯的,所以根本用不到 2 ^ 32 -1。

    2006年11月22日 上午 08:15
    版主

所有回覆

  • 改 Integer 為 Long

    Integer 範圍為 -32768 ~ 32767

    原始碼無需整篇張貼,請把跳出錯誤訊息那行,貼出來,在貼對應的變數宣告即可。

    錯誤的那行微軟出的編譯器預設以黃色標記。

    2006年11月21日 上午 03:15
    版主
  •  

    恩^^ 謝謝大大指教!!

    以下是錯誤訊息&程式碼

    執行階段錯誤 6

    溢位

     

    Dim lns, j, S As Long

    lns = S Mod j

     

    2006年11月21日 上午 11:16
  • VB6 再做宣告時,須明確定義型別

    Dim ins As Long, j As Long, S As Long

    中間不能省略。到了 VBNET 才能省略。

    在出現黃色這行時,你可以把滑鼠游標停留在 ins, S, j 變數上方,會有 Tooltip 跳出變數此時的值,請一併列出。

    2006年11月21日 下午 01:02
    版主
  • 恩^^" 已改進!!

    不過改變宣告之後測試程式時輸入了199(表示計算2到199之間)

    出問題的程式碼:S = (2 ^ i) - 1

    Dim i As Long , S As Long

    S=2147483647

    I=32

    問題一樣是溢位......

    懇請大大指點迷津><~~

    2006年11月22日 上午 03:42
  • VB6 Long 變數值域:-2147483648 ~ 2147483647

    2 ^ 32 = 4294967296

    超出值域,所以溢位。

    算質數幹嘛用到 2 ^ 32 ?

    這邊有個 VBScript 質數的範例:

    http://tlcheng.twbbs.org/TLCheng/Basic/vbs/samples/Prime.htm

    滑鼠右鍵檢視原始碼,貼到 VB6 上可以跑。

    沒用到 2 ^ 32 ,你也可以直接在網頁上執行,比如說上限設為 200。

    2006年11月22日 上午 05:04
    版主
  • 恩...大大您可能誤會了!!

    小弟在網路上找到的判斷質數公式為(2^n-1)

    能夠不被n-1~2這個範圍的數整除就是質數!!

    ex:n=3(被判斷的數)

    (2^3-1)=7

    7不能被6~2這個範圍的數整除

    所以3為質數!!

    是這樣的!!

     

    2006年11月22日 上午 07:35
  • 你的公式有問題。

    求質數的上限也是 Int(Sqr(n)),Int(Sqr(7)) = 2 只要檢查 2 能否整除即可。

    而要整除的對象,是質數,不是 2 ~ 6 ,而是小於等於 Int(Sqr(n)) 的質數。

    所以演算過程要動態建立 2 ~ Int(sqr(n)) 的質數,另外你的推論也有問題:

    ex:n=3(被判斷的數)

    (2^3-1)=7

    7不能被6~2這個範圍的數整除

    所以3為質數!!

    3 可能被大於 3 的整數整除?數學上也不通吧?那 n = 4時,2^4 - 1 = 15

    15 能被 3, 5 整除,所以 3,5 不是質數?或是 3, 5 是質數?

    邏輯整個是錯的,所以根本用不到 2 ^ 32 -1。

    2006年11月22日 上午 08:15
    版主
  • 恩^^ 謝謝大大的建議!!

    小弟將程式改寫了一下~

    發現2^n-1有一些問題!!

    採用大大的算法之後題目已經解決了!!

    感謝!!

    2006年11月22日 下午 11:33