[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}]]
}
} 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**
<<discussion>>
----
----
<<categories>> Numerical Analysis | Toys | Calculator | Mathematics| Example| Toys and Games | Games | Application | GUI
----
<<categories>> Development | Concept| Algorithm | Biology| Documentation | Concept| AI| Algorithm