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 > possiblePrime Then Exit For End If Next primeIndex += 1 myPrimes(primeIndex) = possiblePrime Loop Return myPrimes End Function End Module