Collection vs Array

[Phox]

Hi all,

I've created the function below to create a collection of primes which is based on the Sieve of Erastothenes. The function creates the list fairly quickly; it can produce all primes under one million in less than a second on my PC. Using the collection, I want to be able to A) Test a given number for primality, and B) Iterate through the prime numbers. Collections are able to handle both of these requirements because I can use both keys and indices, however, accessing a large collection with an index is much too slow for my purposes.

Instead of using a collection, I could:
A) Create an array of 1 to n Booleans
This would let me test for primality quickly but would be more slow at iterating through prime numbers.
B) Create an exclusive array of Long type primes
This would let me iterate through primes quickly but would be more slow at determining primality.

Can any of you think of a way to satisfy both requirements in one solution that isn't too slow?

Function PrimesUpTo(n As Long, Optional primes As Collection) As Collection
'Uses Sieve of Erastothenes to create collection of all primes <= n
'Collection has key in the form of "K" & n, so primality can be easily tested
'Fairly efficient at creating primes, but accessing a large colllection is slow

    Dim IsPrime() As Boolean
    Dim i As Long, j As Long, start As Long
    
    'The existing prime collection is larger than requested
    If Not primes Is Nothing Then
        If n <= primes.count Then
            Set PrimesUpTo = primes
    Exit Function
        End If
    End If
    
    'Create a boolean array for primality where default is True
    ReDim IsPrime(n)
    For i = 3 To n Step 2 'No even number is prime except 2
        IsPrime(i) = True
    Next i
    
    'Sieve from existing primes
    If primes Is Nothing Then
        Set primes = New Collection
        primes.Add 2, "K2"
        start = 3
    Else
        For i = 1 To Int(Sqr(primes.count))
            For j = primes.count \ primes(i) To n \ primes(i)
                If IsPrime(j) Then IsPrime(primes(i) * j) = False
            Next j
        Next i
        start = primes(primes.count) + 2
    End If

    'Sieve from newly derived primes
    For i = start To Int(Sqr(n)) Step 2
        If IsPrime(i) Then
            For j = i To n \ i
                IsPrime(i * j) = False
            Next j
        End If
    Next i
    
    'Turn completed Boolean array into collection
    For i = start To n Step 2
        If IsPrime(i) Then primes.Add i, "K" & i
    Next i
    
    Set PrimesUpTo = primes

End Function

 

[FastExcel]

1. its very much faster to iterate over a collection using For Each rather than for j=1 to PrimesCollection.count

2. Dictionaries are usually faster than collections

3. If you have enough memory to handle it then build BOTH a Boolean array and an exclusive array of long primes, that would probably be the fastest solution