A Functional Way of Prime Numbers

The first task in converting existing code to a component is to change the model from functional to object-oriented. Of course, if you’re starting from scratch, you can start out object-oriented but you still need to put yourself in an object state of mind. Most of us still program in functional mode. Here’s how I changed my way of thinking about the sieve of Eratosthenes.

First look at the sieve in functional form. The algorithm shown here is pretty much the same as the one presented in Byte magazine in 1983 and used by hundreds of reviewers in many languages ever since. Variable names have been changed to protect the guilty. The function interface has been changed to accept an array that will be filled with the prime numbers the algorithm finds. The only logical change in the algorithm is that nonprime numbers are marked with True rather than False to take advantage of Visual Basic’s automatic initialization to 0.

Function Sieve(ai() As Integer) As Integer
    Dim iLast As Integer, cPrime As Integer, iCur As Integer, i As Integer
    Dim af() As Boolean
    ‘ Parameter should have dynamic array for maximum number of primes
    If LBound(ai) <> 0 Then Exit Function
    iLast = UBound(ai)
    ‘ Create array large enough for maximum prime (initializing to zero)
    ReDim af(0 To iLast + 1) As Boolean
    For iCur = 2 To iLast
        ‘ Anything still zero is a prime
        If Not af(iCur) Then
            ‘ Cancel its multiples because they can’t be prime
            For i = iCur + iCur To iLast Step iCur
                af(i) = True
            Next
            ‘ Count this prime
            ai(cPrime) = iCur
            cPrime = cPrime + 1
        End If
    Next
    ‘ Resize array to the number of primes found
    ReDim Preserve ai(0 To cPrime) As Integer
    Sieve = cPrime
End Function

The Select Case block of the client program where the function version is called looks like this:

Case estBasicLocalFunction
    ‘ Get all at once
    ms = timeGetTime()
    For i = 1 To cIter
        ReDim ai(0 To cPrimeMax)
        cPrime = Sieve(ai())
        If fDisplay Then
            lstOutput.Clear
            For iPrime = 0 To cPrime - 1
                lstOutput.AddItem ai(iPrime)
                lstOutput.TopIndex = lstOutput.ListCount - 1
                lstOutput.Refresh
            Next
        End If
    Next
    txtTime.Text = timeGetTime() - ms
    txtPrimes.Text = cPrime

Our job is to convert the local sieve function into a local CSieve class. After that, we can worry about converting to other kinds of COM components.