困難素數程序.NET

我試圖寫一個程序，如果你輸入一個號碼，並點擊一個按鈕，程序就能確定號碼是否是一個素數（整除只1和本身）。困難素數程序.NET

當我輸入數字「5」（例如），則程序規定「是」這是一個質數。但是，當我輸入不是素數的「4」時，程序仍然表示是素數。

我不確定我哪裏錯了給出的「如果」語句和循環我寫的。我的代碼如下：

Public Class Form1 
    Private Sub btnCalculate_Click(sender As Object, e As EventArgs) Handles btnCalculate.Click 
     Dim iNum, iSum As Double 
     Dim isPrime As Boolean = True 
     iNum = Convert.ToInt32(tbxN.Text) 
     For i = 2 To (iNum - 1) Step 1 
      iSum = iNum Mod i 
     Next 
     If iSum = 0 Then 
      isPrime = False 
      lblAnswer.Text = "No" 
     Else 
      isPrime = True 
      lblAnswer.Text = "Yes" 
     End If 
    End Sub 
End Class

我相信這可能是我的「如果」語句的問題，而且在循環的程序只使用最後一個值，使素數的決定，但是，我需要它如果iSum是EVER 0，那麼它不是Prime。如果iSum從不爲0，那麼它就是Prime。

我該如何解決這個問題？謝謝！

來源

2014-01-29 user3200800

需要檢查的循環內。如果你發現它不是素數，你可以提早停下來。「 – SLaks

你需要修改你的邏輯，你目前的邏輯覆蓋的iSum的價值，從而導致錯誤的結果。一旦你發現iSum是0，你應該打破你的循環，否則布爾變量isPrime將保持爲假。 （我也改變了varaible isPrime爲false在初始化）

Private Sub btnCalculate_Click(sender As Object, e As EventArgs) Handles btnCalculate.Click 
    Dim iNum, iSum As Double 
    Dim isPrime As Boolean = False 
    iNum = Convert.ToInt32(tbxN.Text) 
    For i = 2 To (iNum - 1) Step 1 
     iSum = iNum Mod i 
     If (iSum = 0) Then 
      isPrime = True 
      Exit For 
     End If 
    Next 
    If isPrime Then 
     lblAnswer.Text = "Yes" 
    Else 
     lblAnswer.Text = "No" 
    End If 
End Sub

您也可以進一步優化您的代碼，通過檢查它循環，直到iNum/2，而不是iNum - 1，甚至更好（在評論中指出）是檢查，直到數的平方根：

For i = 2 To Math.Sqrt(iNum) Step 1

更多關於它的Wikipedia

來源

2014-01-29 18:15:18 Habib

」通過檢查循環直到「iNum/2」來優化「你可以走得更遠，只要到達'iNum'的平方根就停下來。 – dasblinkenlight

單獨檢查2，然後從3步驟2開始將進一步優化。另外我想你會發現使用一個do直到i * i> = inum循環，由於Math.Sqrt的開銷，它會進一步優化。 – tinstaafl

的的數目是否爲素數檢測該算法是不正確：

For i = 2 To (iNum - 1) Step 1 
    iSum = iNum Mod i 
Next 
If iSum = 0 Then 
    isPrime = False 
    ...

它假定一個數是否非素，它將在範圍2整除通過所有號碼.. N-1。對非質數的實際要求可以被任何這個範圍內的數字整除。

儘快你看到它實現這一點，檢查是否iNum Mod i爲零，並停止循環。當iNum Mod i爲零時，設置一個表示「不是素數」的標誌。如果你的循環沒有達到上述條件就完成了，那麼這個數字就是質數。

請注意，您不必檢查範圍2..N-1中的所有數字：如果您檢查了2到包含N（包含）的平方根的數字，並且沒有找到任何除數，則您知道這個數字是素數。

來源

2014-01-29 18:15:39 dasblinkenlight

而且你不需要任何總結，如果你在表示P範圍[2，開方（P）獲得P模X == 0不是素數並停止cicle和回報。

來源

2014-01-29 18:21:19 emcas88

如果你只想要一些有效的東西，這一切都很好。然而，如果你想要更高效的東西，Eratosthenes的篩子工作得很好。這裏有一個函數可以生成一個比特數組，其中索引爲素數的每個元素爲真，其餘爲假。這對於一次使用非常有效，或者對於重複使用更有效。生成一個1,000,000個元素的數組需要大約3毫秒。

Dim Primes As BitArray 
Primes = GeneratePrimes(1000000) 
Dim IsPrime As Boolean = Primes(20) 

Function GeneratePrimes(n As Integer) As BitArray 
    Dim bits = New BitArray(n + 1, True) 
    Dim max = CInt(Math.Sqrt(n)) 
    bits(0) = False 
    bits(1) = False 
    For i As Integer = 2 To max 
     If bits(i) Then 
      For j As Integer = i * i To n Step i 
       bits(j) = False 
      Next 
     End If 
    Next 
    Return bits 
End Function

正如你所看到的，只是索引處元素的檢查值返回true或false。

來源

2014-01-29 20:42:48 tinstaafl

所有提到平方根的人都是正確的，30％。您只需檢查平方根+1（爲了好的測量），但實際節省的時間是您只需將所有PRIMES的數字除以平方根+1。

例如，找出如果23是黃金你把由質數高達平方根+ 1

sqrt(23) = 4.79 so we go to > 5 

23 mod 2 = 1, 
23 mod 3 = 2, 
23 mod 5 = 3, 
23 = prime

因爲沒有模數計算= 0

來源

2014-09-24 09:21:30 Delaney

困難素數程序.NET

回答

相關問題