找出最大素数
找出最大素数
提问于 2014-01-12 17:35:30
我正在编写一个程序，在指定的限制范围内查找素数。我试过：
Sub Main()
Console.WriteLine("Enter the maximum")
Dim primes As List(Of Integer) = New List(Of Integer)
Dim m As Integer = Console.ReadLine()
Dim odds As List(Of Integer) = GetOdds(m)
For Each i In odds
Dim x As List(Of Integer) = GetFactors(i)
Dim con As Boolean = (x(0).ToString().Contains(i) Or x(1).ToString().Contains(i))
If x.Count = 2 Then
primes.Add(i)
' *****
End If
Next
Console.WriteLine("The primes are: " + String.Join(", ", primes))
Console.ReadLine()
End Sub
Function GetOdds(ByVal max As Int32) As List(Of Integer)
Dim g As List(Of Integer) = New List(Of Integer)
For i = 2 To max
If i Mod 2 = 0 Then
Continue For
Else : g.Add(i)
End If
Next
Return g
End Function
Function GetFactors(ByVal x As Integer) As List(Of Integer)
Dim factors As List(Of Integer) = New List(Of Integer)
Dim max As Integer = Math.Sqrt(Convert.ToDouble(x))
For i = 1 To max
If x Mod i = 0 Then
factors.Add(i)
If i <> x / i Then
factors.Add(i / x)
End If
End If
Next
Return factors
End Function但是当我运行它时，程序会跳过2。如何解决这个问题？我试着补充：
primes.Insert(0, 2)在我用星号标记的代码区域。
但那样的话，程序就会输出太多的2。
我该怎么办？谢谢。
回答 2
Stack Overflow用户
回答已采纳
发布于 2014-01-12 17:49:49
你只是在检查奇数是否是素数。2是偶数，所以这就是为什么程序要省略它。因此，您应该初始化您的集合，以便它已经包含2(它是唯一的偶数素数)：
Dim odds as List(Of Integer)
odds.Add(2)然后添加GetOdds(i)
Stack Overflow用户
发布于 2014-01-13 17:26:47
虽然您的代码看起来会工作，但您会发现，为更大的数字寻找素数将需要相当长的时间。
一种改进型的Eratosthenes筛子对此效果很好。
而不是用奇数和2在主循环中列出奇数来检查起始数。
Dim primes As List(Of Integer) = New List(Of Integer)
primes.Add(2)
For i = 3 To m Step 2
If IsPrime(i) Then
primes.Add(i)
End If
Next
Dim Sieve As New List(Of Integer)({2, 3, 5, 7, 11, 13})
Function IsPrime(num As Integer) As Boolean
If num = 1 Then Return False
'If number is in the sieve it's prime
If Sieve.Contains(num) Then Return True
'Set limit to the square root of the numnber
Dim Max As Integer = CInt(Math.Sqrt(num))
'Since every num will be odd, there's no need to check if it's divisible by 2
Dim I As Integer = 1
'Check if the number is a multiple of any elements in the sieve
While (I < Sieve.Count AndAlso Sieve(I) <= Max)
If (num Mod Sieve(I) = 0) Then Return False
I += 1
End While
'If the number is too big for the sieve to adequately check, build the sieve bigger,
'and check the number against the new primes.
If Max > Sieve.Last Then
For J As Integer = Sieve.Last + 2 To Max Step 2
Dim good As Boolean = True
For K = 0 To Sieve.Count - 1
If J Mod Sieve(K) = 0 Then
good = False
Exit For
End If
Next
If good Then
Sieve.Add(J)
If num Mod J = 0 Then Return False
End If
Next
End If
Return True
End Function基本上，这是从前6个素数的列表开始，并使用它来检查质数，根据需要构建更大的质数。找到1000000的素数大约需要1秒。由于列表在每次向其添加素数时都在类级别，因此它有助于对函数的连续调用。
当然，更真实地实现Eratosthenes的筛子甚至更好：
Function GeneratePrimes(n As Integer) As List(Of Integer)
Dim bits = New BitArray(n + 1, True)
Dim primes = New List(Of Integer)
bits(0) = False
bits(1) = False
For i As Integer = 2 To CInt(Math.Sqrt(n))
If bits(i) Then
For j As Integer = i * i To n Step i
bits(j) = False
Next
primes.Add(i)
End If
Next
For i = CInt(Math.Sqrt(n)) + 1 To n
If bits(i) Then
primes.Add(i)
End If
Next
Return primes
End Function页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/21077945
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号