この問題は6の剰余で分類すると速いです。なぜなら、12以上の6の倍数はすべて過剰数だからです。
144秒かかりました。
function fold($f, $x0) {
begin { $x = $x0 }
process { $x = &$f $x $_ }
end { $x }
}
function div_pow($n, $d) {
$e = 0
while($n % $d -eq 0) {
++$e
$n /= $d
}
($e, $n)
}
function factorize($n, $p0 = 2) {
if($n -gt 1) {
for($p = $p0; $p * $p -le $n; ++$p) {
if($n % $p -eq 0) {
$e, $m = div_pow $n $p
,@($p, $e)
factorize $m ($p + 1)
return
}
}
,@($n, 1)
}
}
function pow($p, $e) {
$y = 1
for($k = 0; $k -lt $e; ++$k) {
$y *= $p
}
$y
}
function is_abundant($n) {
function f($x) {
$p, $e = $x
1..$e | fold { $args[0] * $p + 1 } 1
}
$fs = factorize($n)
if($fs[0].GetType().Name -eq "Int32") {
$fs = ,$fs
}
$a = $fs | fold { $args[0] * (f $args[1]) } 1
$b = $fs | fold { $args[0] * (pow $args[1][0] $args[1][1]) } 1
$a -gt $b * 2
}
$watch = New-Object System.Diagnostics.Stopwatch
$watch.Start();
$L = 28123
$g = 1..6 | foreach { ,@() }
foreach($n in 2..$L) {
if(is_abundant $n) {
$r = $n % 6
$g[$r] += $n
}
}
$a = 0..$L | foreach { 1 }
foreach($r in 0..5) {
if($g[$r].length -gt 0) {
$head = $g[$r][0]
for($k = $head + 12; $k -le $L; $k += 6) {
$a[$k] = 0
}
}
foreach($r1 in 1..5) {
$r2 = ($r - $r1 + 6) % 6
if($r2 -gt $r1) { continue }
foreach($p in $g[$r1]) {
if($p -gt $L) {
break
}
foreach($q in $g[$r2]) {
if($p + $q -gt $L) {
break
}
$a[$p+$q] = 0
}
}
}
}
(1..$L | where { $a[$_] -eq 1 } | measure -sum).sum
$watch.Stop();
$watch.Elapsed.TotalMilliSeconds / 1000
