[Shootout-list] Tcl : nsieve

[Robert Seeger]

I updated the Tcl implementation of the nsieve test. It now uses
lists, since they are closer to a C array than Tcl arrays are.
However, even with N = 3, it takes over 2 minutes to complete on my
system :(

Rob Seeger



package require Tcl 8.4

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 1} {$i <= $n} {incr i} {
        lappend data $i
    }

    for {set i 2} {$i <= $n} {incr i} {
        if { [string length [lindex $data $i]] } {
            for {set j [expr {$i * $i}]} {$j <= $n} {incr j $i} {
                if { [string length [lindex $data $j]] } {
                    lset data $j {}
                }
            }
        }
    }
    
    expr {[lsearch [lsort -decreasing $data] {}] -2}
}

main [lindex $argv 0]