Windows PowerShellでProject Euler（33）

PowerShell

Problem 26

剰余類群で10が生成元になる最も大きい素数を求めればよいのですが、なるべく手抜きすることを考えます。10と互いに素で、gp-1で初めて1になればよいです。これを素直に書きました。

filter next() {
    $_
    throw
}

function gcd($n, $m) {
    if($m -eq 0) { $n } else { gcd $m ($n % $m) }
}

function is_generator($g, $p) {
    if((gcd $g $p) -ne 1) {
        return $false
    }
    
    $n = 1
    for($k = 1; $k -lt $p - 1; ++$k) {
        $n = $n * $g % $p
        if($n -eq 1) {
            return $false
        }
    }
    return $true
}

999..2 | where { is_generator 10 $_ } | next
trap { continue }