Windows PowerShellでProject Euler（36）

これは手計算でできる問題です。べき乗の計算をしてはいけません。
function gcd($n, $m) {
    if($m -eq 0) { $n } else { gcd $m ($n % $m) }
}

function int_log($n, $b) {
    $e = 0
    $p = 1
    while($p -le $n) {
        $e += 1
        $p *= $b
    }
    $e - 1
}

# 指数ごとにべき乗数の個数を求める
# $N = 10ならべき乗数は2^2, 2^3, 3^2だから
# 2乗は2個、3乗は1個
# @(0, 0, 2, 1)となる
function num_powers($N) {
    $pows = @{ }    # べき乗数の集合
    for($b = 2; $b * $b * $b * $b -le $N; ++$b) {
        for($p = $b * $b; $p * $p -le $N; $p *= $b) {
            $pows[$p] = 1
        }
    }
    
    $a = @()        # 各底で最大の指数
    for($b = 2; ; ++$b) {
        if($pows[$b] -ne $null) { continue }
        $emax = int_log $N $b
        if($emax -eq 1) { break }
        $a += $emax
    }
    
    $b = @(0) * ($a[0] + 1)
    foreach($emax in $a) {
        foreach($e in 2..$emax) {
            $b[$e] += 1
        }
    }
    $b
}

# 指数$eが与えられたとき、
# 2^$eの$N乗までの数でより大きなべき乗で表せるものの個数を返す
function overlap($e, $N) {
    $a = @(0) * ($N + 1)
    foreach($e1 in 1..($e-1)) {
        $d = $e1 / (gcd $e1 $e)
        if($d -eq 1) { $k0 = 2 } else { $k0 = $d }
        for($k = $k0; $k * $e -le $N * $e1; $k += $d) {
            $a[$k] = 1      # 表せる
        }
    }
    
    ($a | measure -sum).sum
}

$N = 100
$nes = num_powers $N
$overlaps = (2..($nes.length - 1) | foreach { (overlap $_ $N) * $nes[$_] } |
                                                            measure -sum).sum
($N - 1) * ($N - 1) - $overlaps