Prime Numbers

[Oorang]

I poseted this over at the lounge because it is more something I was tinkering with for fun. I wass helping a friend with her homework and she had to do a program to output prime numbers. The first solution that came to mind was a simple brute force approach. But the more I got thinkg about it the deeper I realized the problem went. You don't ever need to test even numbers past and I found someone elses solution showing how you could avoiding testing multiples of 3 by alternating your increment by 2 and 4 in turn. Then it occured to me I didn't need to test WITH any number other than a prime number. And I only need to test up to the square root of the number being tested. However it still feels like this could be done better. I was wondering if anyone could take a peek at what I have and lend any thoughts on how to speed it up?

Option Explicit
Sub OuputPrime()
Dim TestedNumber As Double
Dim TestingLimit As Double
Dim LoopCount As Double
Dim PrimeArray() As Double
Dim IsPrime As Boolean
Dim Increment As Byte
Dim T As Date
On Error GoTo exitlight
T = Time
On Error Resume Next
TestingLimit = InputBox("Find primes up to what number?", "Prime List", 1E+16)
If TestingLimit = 0 Then Exit Sub
ReDim PrimeArray(1)
PrimeArray(0) = 2
PrimeArray(1) = 2
Range("a1") = 2
Range("a2") = 3
TestedNumber = 5
Do Until TestedNumber > TestingLimit
    If Increment = 2 Then Increment = 4 Else: Increment = 2
    IsPrime = True
    For LoopCount = LBound(PrimeArray) To UBound(PrimeArray)
        If PrimeArray(LoopCount) > Int(Sqr(TestedNumber)) Then Exit For
        If TestedNumber Mod PrimeArray(LoopCount) = 0 Then
            IsPrime = False
            Exit For
            End If
    Next LoopCount
    If IsPrime = True Then
        ReDim Preserve PrimeArray(UBound(PrimeArray) + 1)
        PrimeArray(UBound(PrimeArray)) = TestedNumber
        ActiveSheet.Cells(UBound(PrimeArray) + 1, 1) = TestedNumber
        End If
TestedNumber = TestedNumber + Increment
Loop
exitlight:
End Sub

 

[PaddyD]

how about:

=OR(A1=2,A1=3,ISNA(MATCH(TRUE,A1/ROW(INDIRECT("2:"&INT(SQRT(A1))))=
INT(A1/ROW(INDIRECT("2:"&INT(SQRT(A1))))),0)))


as a test for primeness?

see:

http://j-walk.com/ss/excel/eee/eee015.txt

 

[erik.van.geit]

Hi, Oorang,

since a long time this is on my computer
dated from a period when I was so stupid not to check if the author had put his name within the code and to write the source (web ?) in the file itself
oh! just checked the properties of the file
author: Nico Sterk
created: 23 oct 2001 15:51:43

remarks
some errorhandling missing (not important)
putting everything in an array before writing to the sheet would speed it up

Option Explicit

Sub StartSieve(ByVal MinPrime As Long, ByVal MaxPrime As Long)
    'Cand = 3,5,7,9,11,13,
    'Cand = Index*2+1
    'Index = 1,2,3,4,5,
    'Index=(Cand-1)/2
    Dim MaxIndex As Long
    Dim Cand As Long
    Dim Index As Long
    Dim Remove As Long
    Dim Sqrt As Double
    Dim Pointer As Long
    Pointer = 0
    ActiveWindow.ScrollRow = 1
    ActiveWindow.ScrollColumn = 1
    For Cand = 2 To 3
        If Cand > MinPrime Then
            WriteNext Cand, Pointer
            Pointer = Pointer + 1
        End If
    Next Cand
    MaxIndex = (MaxPrime - 1) / 2
    ReDim prime(1 To MaxIndex) As Boolean
    For Index = 1 To MaxIndex
        prime(Index) = True
    Next Index
    Sqrt = Sqr(MaxPrime)
    Cand = 3
    While Cand < MaxPrime
        If Cand <= Sqrt Then
            Remove = Cand * Cand
            While Remove <= MaxPrime
                prime((Remove - 1) / 2) = False
                Remove = Remove + 2 * Cand
            Wend
        End If
        Cand = Cand + 2
        If Cand >= MaxPrime Then
            MsgBox (CStr(Pointer) + " primes found")
            Exit Sub
        End If
        While Not prime((Cand - 1) / 2)
            Cand = Cand + 2
            If Cand >= MaxPrime Then
                MsgBox (CStr(Pointer) + " primes found")
                Exit Sub
            End If
        Wend
        If Cand > MinPrime Then
            WriteNext Cand, Pointer
            Pointer = Pointer + 1
        End If
    Wend
End Sub

Sub WriteNext(ByVal Num As Long, ByVal Pointer As Long)
    Const RowOffset = 10
    Const ColNum = 250
    Dim Row As Long
    Dim Col As Long
    Col = (Pointer) Mod ColNum + 1
    Row = (Pointer) \ ColNum + 1
    Cells(Row, Col).Value = Num
    If Col = 1 And Row > RowOffset Then
        ActiveWindow.ScrollRow = Row - RowOffset
    End If
End Sub

Sub WritePrimes()
    ActiveSheet.UsedRange.Clear
    Dim MinPr As Long
    Dim MaxPr As Long
    MinPr = CLng(InputBox("Calculate all primes greater than:", "Minimum", "0"))
    While MaxPr < 3
        MaxPr = CLng(InputBox("and less than:", "Maximum", "3"))
    Wend
    If MaxPr Mod 2 = 0 Then
        MaxPr = MaxPr - 1
    End If
    StartSieve MinPr, MaxPr
End Sub

kind regards,
Erik

 

[erik.van.geit]

found it !!
http://members.chello.nl/n.sterk/ExcelPages/Files/excel_files.htm

 

[Andrew Fergus]

Hi Oorang

I did a very similar thing using Python some years ago and used an almost identical methodology. The divisor started at 3 and was changed to the next prime number until I reached the square root of the numerator (I only tested the odd numbers). What I did differently was store the first 4,203 (excluding 2) prime numbers in a text file and these were imported into an array whenever the programme was started. This gave me a list of divisors from 3 to 40,009. This allows you to test numerators up to the value of 1.6 billion (i.e. 40k^2). To test higher numbers I increased the size of the array and imported more denominators.

To speed up the code do 2 things : minimise the number of commands inside the main loop and don't perform any file read or write tasks (use an array instead) inside the main loop. In my Python programme I did have a file write inside my main loop which slowed the process but hey I was still learning....

My main loop logic for testing to see if a series of numbers were primes or not went like this (Python syntax, not converted to VBA) :

while numerator < maxtestnum :                    ## testing up to maxtestnum
        if numerator%divisor[count] == 0 :                   ## not a prime
            count = 0                                   ## reset divisor array pointer
            numerator = numerator + 2                             ## increment test number
        else :
            if (divisor[count+1]) > (numerator/(divisor[count+1])) : ## is prime
                primenew.append(numerator)                   ## store new prime
                count = 0                               ## reset divisor array pointer
                numerator = numerator + 2                         ## increment test
            else :                                      ## further testing required
                count = count + 1                       ## select next divisor in the array

The logic is simple enough to follow even without the VBA endif statements. The reason I didn't flip flop the 2 and 4 was because numbers divisible by 3 would fail at the first step in the test and it meant one less if statement in the main loop.

HTH, Andrew

 

[shades]

Interesting.

Here are two sites that gives the mathematical background

to finding primes.

Finding Primes and Proving Primality