[Shootout-list] Shootout submission: Tcl: nsieve

[Robert Seeger]

Below is a simple submission for the nsieve test of the shootout. It
uses dicts, which are a feature of Tcl 8.5. I'd like to make the
recommendation that, where possible, Tcl shootout submissions use the
ActiveTcl 8.5.0b3 distribution, since it includes the many new
features of Tcl 8.5, as well as being optimized for speed (at least,
from my experience).

Rob Seeger


proc main {n} {
    foreach value [list $n [incr n -1] [incr n -1]] {
        set num [expr { int(pow(2, $value) * 10000) }]
        puts [format "Primes up to %8d %8d" $num [nsieve $num]]
    }
}

proc nsieve {n} {
    set data {}
    for {set i 2} {$i <= $n} {incr i} {
        lappend data $i {}
    }

    for {set i 2} {$i <= $n} {incr i} {
        if { ! [dict exists $data $i] } {
            continue
        }
        for {set j [expr {$i * $i}]} {$j <= $n} {incr j $i} {
            dict unset data $j
        }
    }

    llength [dict keys $data]
}

main [lindex $argv 0]