Решение #29

условие
Время работы:

• 21336 микросекунд (0.021336 секунды) на P4 3 ГГц
• 336995 микросекунд (0.336995 секунды) на КПК Acer n311

namespace eval 029 {
    puts [time {
        set edge 100
        set answer 0
        for {set i 2} {$i <= $edge} {incr i} {
            set notpower($i) 1
        }

# ищу представление числа в диапазоне от 2 до $edge
# как максимальную целую степень числа из того же
# диапазона. Алгоритм похож на решето Эратосфена.


        set count 0
        for {set i 2} {$i <= $edge} {incr i} {
            if {$notpower($i)} {
                set j $i
                set j [expr {$j*$i}]
                set k 1
                while {$j<=$edge} {
                    incr k
                    set notpower($j) 0
                    set j [expr {$j*$i}]
                }
                set power($i) $k
            }
        }

# далее имеем представление 2,3,4,5,...
# в виде 21,31,22,51,...
# очевидно, что если основания у двух чисел в этом представлении разные, то
# при любых целых показателях получаются разные числа. Если показатели
# совпадают, то возможны коллизии. Их устраняет следующий код:


        foreach key [array names power] {
            if {[array exists used]} {
                array unset used
            }
            for {set i 1} {$i<=$power($key)} {incr i} {
                for {set j 2} {$j <= $edge} {incr j} {
                    set used([expr {$i*$j}]) 1
                }
            }
            incr answer [llength [array names used]]
        }
        puts $answer
    }]
}

Код распространяется по лицензии CC-NC-BY (creative commons)