Find Prime Numbers up to a maximum

Question

I am writing a program that finds prime numbers up to a specified limit. I have tried:

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

But when I run it, the program skips 2. How may I fix this issue? I tried to add:

primes.Insert(0, 2)

at the area in the code that I marked with asterisks.

But then the program would output too many 2's.

What should I do? Thank you.

Answer 1

While your code looks like it will work, you'll find that, finding primes for larger numbers will take a considerable amount of time.

A modified Sieve of Eratosthenes will work well for this.

Instead of making a list of odd numbers to check against start with an odd number and step by 2 in the main loop.

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

Basically this starts with a list of the first 6 primes and uses it to check for prime, building it bigger as needed. Finding all the primes up to 1000000 takes about 1 sec. Since the list is at the class level every time a prime is added to it it helps successive calls to the function.

Of course a truer implementation of the Sieve of Eratosthenes works even better:

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

Answer 2

You are only checking if odd numbers are prime. 2 is even, so that is why the program is omitting it. So you should initialize your collection so that it already contains 2(it is the only even prime number):

Dim odds as List(Of Integer)
odds.Add(2)

And then add GetOdds(i)