Prime Numbers

[appi101]

Hi

What would be the fastest way of finding primes numbers. I was able to find 10 million of them in 4762 secs on a p3-866 on win98.

Appi

[Nucleus]

What is the code you are currently using? Then we can see if it can be optimised.

[appi101]

Hi

THanks for the reply. Here's the source code.

Appi

[kedaman]

That's pretty much the fastest way to retrieve the primes, in two ways, 1. You check if it is divisble with earlier found primes effectively eliminating checks with numbers that can be factorized with earlierly checked primes. 2. No need to go beyond the squareroot of the value to check since the factors always comes in pairs where the highest possible pair can not exceed the root. So the algoritm is very optimized.
Anyway implementing it vb slows it down, here's what I did to remove the bottlenecks:
1. Replaced all double precision floating points except the timer with long integers. replaced t string with long, yes that inexcusable misstake.
2. Inlined the IsPrime function, the stack processing in vb is heavy. The extra Do-Loop is just there to function as a exit point.
3. Narrowed the UI processing by 1000, the refreshing of the label as well as processing messages with doevents is quite a hog.

Dim Total As Long
Dim TotalAsYet As Long
Dim Primes() As Long
Option Explicit

Private Sub Command1_Click()
Dim Tmr As Double, i&, ff%, t&, t2$, x&, root&, IsPrime As Boolean
Tmr = Timer
t2 = InputBox("How Many Primes do you want")
If t2 = "" Then Exit Sub
t = Val(t2)
ReDim Preserve Primes(1 To t)
Primes(1) = 2
i = 3
TotalAsYet = 1
Label1.Caption = "Calculating"
ReDim Preserve Primes(1 To t)
Do
    Do
        root = Sqr(i)
        For x = 1 To TotalAsYet
            If Primes(x) <= root Then
                If i Mod Primes(x) = 0 Then
                    IsPrime = False
                    Exit Do
                End If
            Else
                IsPrime = True
                Exit Do
            End If
        Next
        IsPrime = True
    Loop While False
    
    If IsPrime Then
        TotalAsYet = TotalAsYet + 1
        Primes(TotalAsYet) = i
        If i Mod 1000 = 1 Then
            lblprog.Caption = TotalAsYet / t * 100
            DoEvents
        End If
    End If
    i = i + 2
Loop While (TotalAsYet <> t)
lblprog.Caption = "Time Taken " & Timer - Tmr
ff = FreeFile
Open "c:\primes.txt" For Output As ff
Label1.Caption = "Writing"
    For i = 1 To TotalAsYet
        Print #ff, Str(Primes(i))
        DoEvents
    Next i
Close #ff
Label1.Caption = "Finished"

End Sub

17 secs on a AMD7-600 on win98 for 100000 primes

[kedaman]

I forgot to compile. Here's results from the compiled apps with 100000 primes:
39.9 secs with the bottlenecks
5.2 secs without
762% more efficient

As said, the algoritm was very optimized, it's just the implementation that was bad.

[Nucleus]

Finally got your code (was away from pc yesterday pm). I haven't timed this algorithm or checked to see how scalable it is, but here is an alternative function for you:

Option Explicit
 
Function PrimeArray(numberOfPrimes As Long) As Long()
    Dim found As Long, n As Long, i As Long, sr As Long
    
    '// we know the size of the result in advance
    ReDim result(1 To numberOfPrimes) As Long
    
    '// "2" is the first prime number
    result(1) = 2: found = 1
    n = 1
    
    Do While found < numberOfPrimes
        '// all other prime numbers are odd, so we can skip even numbers
        n = n + 2
        sr = Sqr(n)
        
        '// let's check if N is a prime number
        For i = 1 To found
            
            If (n Mod result(i)) = 0 Then Exit For
            
            If result(i) >= sr Then
                'canot have factor > square root, so n must be prime
                found = found + 1
                result(found) = n
                Exit For
            End If
        
        Next
 
    Loop
    PrimeArray = result
End Function

Usage:

Private Sub Command1_Click()
Dim a, i&
a = PrimeArray(100000)
For i = 1 To UBound(a)
    Debug.Print a(i)
Next
 
End Sub

[appi101]

Hi

What is the meaning of stack processing?

Thanks a lot for the code.

Appi

[kedaman]

It is something your app does to allocate/deallocate memory for each of your function variables and parameters, it's all lowlevel stuff so nothing a vb programmer should worry about. It does take about 100 cpu cycles so it can be considered a hog if called really frequently.

[appi101]

Hi

Thanks a lot for the assistance.

Appi