Generating N Prime Numbers

Question

I'm trying to generate N prime numbers where my N = 200,000.

The method that I think I wrote is -

1. Start with first prime of 2
2. Increment possible prime number by 1
3. See if possible prime is divisible by any found prime (if yes exit to 2)
4. Stop testing when next found prime is more than half of the possible prime (exit to 2)
5. Add it to the list

It works, but it is taking 1 minute 8 seconds which seems really long. Is my algorithm not doing what I think or is it just implemented incorrectly? Or should I not be using these arrays?

Option Explicit On
Option Strict On
Option Infer On
Option Compare Text
Module PrimeNumberGenerator
     Sub Main()
        Static start_time As DateTime
        Static end_time As DateTime
        Dim elapsed_time As TimeSpan
        start_time = DateTime.Now
        Dim targetPrimes(199999) As Integer
        targetPrimes = GetPrimes(targetPrimes.Length)
        end_time = DateTime.Now
        elapsed_time = end_time - start_time
        Debug.Print(elapsed_time.ToString)
        Debug.Print((targetPrimes(500)).ToString)
    End Sub

    Private Function GetPrimes(ByVal countOfPrimes As Integer) As Integer()
        Dim myPrimes(countOfPrimes - 1) As Integer
        Dim primeIndex As Integer = 0
        Dim testIndex As Integer = 0
        Dim possiblePrime As Integer = 2
        myPrimes(primeIndex) = possiblePrime
        Do Until primeIndex = countOfPrimes - 1
            possiblePrime += 1
            For testIndex = 0 To primeIndex
                If possiblePrime Mod myPrimes(testIndex) = 0 Then
                    Continue Do
                ElseIf myPrimes(testIndex + 1) * 2 > possiblePrime Then
                    Exit For
                End If
            Next
            primeIndex += 1
            myPrimes(primeIndex) = possiblePrime
        Loop
        Return myPrimes
    End Function
End Module

Answer 1

One speed tweak is to search to only the square root of the 'possiblePrime'. This will reduce computation by a significant order of magnitude.

Another tweak is to add 2, instead of 1 to 'possiblePrime' as you know that all even numbers > 2 are not prime.

Answer 2

I prefer 'elegant loops' - code that does not have implicit or explicit breaks. Not always easy to achieve, and there are times when it appears impossible. I also prefer 'positive loops' where the continuation is based on a positive explicit statement rather than a negative or combination of negative statements. Sometimes this latter preference can be satisified through a slight tweak of a variable.

I have been looking at the inner For loop, it has two breaks in continuity (Continue Do and Exit For).

    Do Until primeIndex = countOfPrimes - 1
        possiblePrime += 1
        For testIndex = 0 To primeIndex
            If possiblePrime Mod myPrimes(testIndex) = 0 Then
                Continue Do
            ElseIf myPrimes(testIndex + 1) * 2 > possiblePrime Then
                Exit For
            End If
        Next
        primeIndex += 1
        myPrimes(primeIndex) = possiblePrime
    Loop

Which could also be achieved by:

    Dim continueLooking as Boolean, primeFound as Boolean ' loop management
    Do Until primeIndex = countOfPrimes - 1
        possiblePrime += 1
        testIndex = 0
        continueLooking = True
        primeFound = True ' seems counterintuitive to start off at True!
        While continueLooking
            'First check
            If possiblePrime Mod myPrimes(testIndex) = 0 Then
                continueLooking = False
                primeFound = False
            Else
            'Second check
                continueLooking = (Math.Pow(myPrimes(testIndex + 1),2) > possiblePrime)
            End If
        End While 'Wend
        If primeFound then
            primeIndex += 1
            myPrimes(primeIndex) = possiblePrime
        End If
    Loop

Obviously, some more internal management has been used to achieve the elegance, trade-offs always exist.

Answer 3

If speed is an issue, you could use a random number generator followed by a primality test, this is usually faster for big numbers, but if you stay limited to 32 bits ones I'm not sure if it will be faster.

Answer 4

Just implementing AJD's recommendations (compare to square root of test value, add 2 each time). This should be significantly faster.

Private Function GetPrimes(ByVal countOfPrimes As Integer) As Integer()
    Dim myPrimes(countOfPrimes - 1) As Integer
    Dim primeIndex As Integer = 0
    Dim testIndex As Integer = 0
    Dim possiblePrime As Integer = 1
    myPrimes(0) = 2
    Do Until primeIndex = countOfPrimes - 1
        possiblePrime += 2
        For testIndex = 0 To primeIndex
            If possiblePrime Mod myPrimes(testIndex) = 0 Then
                Continue Do
            ElseIf myPrimes(testIndex) >= Math.Sqrt(possiblePrime) Then
                Exit For
            End If
        Next
        primeIndex += 1
        myPrimes(primeIndex) = possiblePrime
    Loop
    Return myPrimes
End Function