Paginated sieving of prime numbers

[Olli]

Hello, this thematic was already seen, seven years ago. But it was a very high level condensed algorithm. Here is a simple sieving of the first million of prime numbers (1 << 20), using the pagination. In this example, each page is 64000 cells sized (1 << 16)

Even if I did not optimize the 2N, this code finds a interest to show you a true pagination, and let any coder to adjust easily the page size to a prime-factor (ex : 2*3*5*7*11*13).

Code: Select all

Delay(16)

tInitial = ElapsedMilliseconds()

sievePageSize = 1 << 16
primeListSize = 1 << 20
sievePageLimit = sievePageSize - 1
primeListLimit = primeListSize - 1

Global Dim sievePage.i(sievePageLimit)

Global Dim prime.i(primeListLimit)
Global Dim primeSieve.i(primeListLimit)

natural = 2
primeLast = 0

sievePageOffset = 0
Repeat
    Repeat
        If sievePage(natural - sievePageOffset) = 0
            
            primeLast + 1
            If primeLast > primeListLimit
                primeLast - 1
                Break 2
            EndIf
            prime(primeLast) = natural
            
            sieve = natural * natural
            While sieve =< sievePageLimit
                sievePage(sieve - sievePageOffset) = 1
                sieve + natural           
            Wend    
            primeSieve(primeLast) = sieve
        EndIf
        natural + 1
    Until (natural - sievePageOffset) > sievePageLimit
    
    sievePageOffset + sievePageSize
    For i = 0 To sievePageLimit
        sievePage(i) = 0
    Next
    For i = 1 To primeLast
        j = (primeSieve(i) - sievePageOffset)
        While j =< sievePageLimit
            If j < 0
                Break
            EndIf
            sievePage(j) = 1
            j + prime(i)
        Wend
        primeSieve(i) = j + sievePageOffset
    Next
ForEver

tFinal = ElapsedMilliseconds()

For i = 1 To primeLast
    ratio.d = i / prime(i)
    ;Debug Str(i) + ": " + Str(prime(i) ) + Chr(9) + StrD(ratio)
Next

MessageRequester("#" + Str(primeLast) + " : " + Str(prime(primeLast) ), Str(tFinal - tInitial) )