[Keith Vetter] - 2024-02-15 I recently came across a https://www.youtube.com/watch?v=fwxjMKBMR7s%|%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}]]
                set pool [lsort -integer -index 1 $pool]
            }
        } 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"

======