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 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"