# 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 -

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
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


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.

• I can't put my finger on it yet, but the inner For loop doesn't appear as elegant as I think it could be.
– AJD
Commented Mar 7, 2018 at 5:11
• Just those two points alone got the process down to under 1 second. Huh. Commented Mar 8, 2018 at 3:07

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.

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.

– Toto
Commented Mar 7, 2018 at 9:21

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

• Nope. possiblePrime starts at 1, adds 2 each iteration. Commented Mar 8, 2018 at 4:23
• Yeah, I was reading it like mine, sorry Commented Mar 8, 2018 at 4:24