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

The method that I think I wrote is -


  
  Start with first prime of 2
  Increment possible prime number by 1
  See if possible prime is divisible by any found prime (if yes exit to 2)
  Stop testing when next found prime is more than half of the possible prime (exit to 2)
  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 &gt; possiblePrime Then
                    Exit For
                End If
            Next
            primeIndex += 1
            myPrimes(primeIndex) = possiblePrime
        Loop
        Return myPrimes
    End Function
End Module
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.