Dijkstra's Prime Algorithm

Keith Vetter - 2024-02-15 I recently came across a Youtube video describing a clever algorithm by Dijkstra to compute all primes less than some number. It has the efficiency of the Sieve of Eratosthenes (see Eratosthenes Sieve) but uses much less memory.

It doesn't need a huge array where we cross off multiples of primes. Instead it uses more of a dynamic programming approach with a simple list of duples called "pool".

When we're considering if number N is prime or not, the list "pool" consists of prime/factor pair where prime is one of the primes we've found so far and factor is the smallest factor of that prime greater or equal to N.

If N is smaller than all the factors, then it must be prime--and we need to add it to "pool". Otherwise it's composite--and we need to update "pool" so all factors are greater or equal to n+1.

proc FindPrimes {max} {
    set pool [list {2 4}]
    set primes [list 2]

    for {set k 3} {$k < $max} {incr k} {
        # if {$k % 10000 == 0} { puts "$k/$max" ; flush stdout}
        if {$k < [lindex $pool 0 1]} {
            lappend primes $k
            if {$k * $k <= $max} {
                lappend pool [list $k [expr {$k * $k}]]
            }
        } else {
            for {set idx 0} {$idx < [llength $pool]} {incr idx} {
                lassign [lindex $pool $idx] n factor
                if {$factor > $k} break

                lset pool $idx 1 [expr {$factor + $n}]
            }
            set pool [lsort -integer -index 1 $pool]
        }
    }
    return $primes
}
set start [clock milliseconds]
set all [FindPrimes 1000000] ; list
set end [clock milliseconds]
set duration_seconds [expr {($end - $start) / 1000.0}]
puts "It took $duration_seconds to compute [llength $all] primes"

gold 4/3/2024. Made no changes to above code. Added some categories, so this interesting page could be found in the Wiki stacks.

Hidden Comments Section