Lucas-Carmichael numbers: Difference between revisions
→{{header|Raku}}: better performance (~3x faster)
m (→{{header|Python}}: use the built-in `pow(b,-1,m)` for computing the modular inverse (faster)) |
(→{{header|Raku}}: better performance (~3x faster)) |
||
Line 588:
<syntaxhighlight lang="raku" line># 20231224 Raku programming solution
▲sub primorial($n) { [*] @primes[^$n] }
▲sub divceil ($x, $y) { ($x %% $y ?? 0 !! 1) + $x div $y } # ceil(x/y)
return $ud % $modulo;▼
sub LC_in_range ($A is copy, $B, $k) {
my ($max_p, @LC) = Int(sqrt($B + 1) - 1);
$A = max(primorial($k + 1) +> 1, $A);
sub SUB($m, $L, $lo is copy, $k) {
if $k == 1 {
my $hi = min($
$lo = max($lo, divceil($A, $m));
my $t = $L -
$t += $L while $t < $lo;
for $t, $t+$L ... $hi -> $p {
Line 632 ⟶ 615:
return;
}
for
if $p.is-prime and ($m gcd ($p + 1)) == 1 {
SUB($m * $p, ($L lcm ($p + 1)), $p + 1, $k - 1)
}
}
};
SUB(1, 1, 3, $k);
|