Blum integer: Difference between revisions

=={{header|Perl}}==

{{trans|Raku}}

{{libheader|ntheory}}

<syntaxhighlight lang="perl" line>

use v5.36;

use enum <false true>;

use ntheory <is_prime gcd>;

sub comma { reverse ((reverse shift) =~ s/.{3}\K/,/gr) =~ s/^,//r }

sub table ($c, @V) { my $t = $c * (my $w = 5); ( sprintf( ('%'.$w.'d')x@V, @V) ) =~ s/.{1,$t}\K/\n/gr }

sub is_blum ($n) {

return false if $n < 2 or is_prime $n;

my $factor = find_factor($n);

my $div = int($n / $factor);

return true if is_prime($factor) && is_prime($div) && ($div != $factor) && ($factor%4 == 3) && ($div%4 == 3);

false;

}

sub find_factor ($n, $constant = 1) {

my($x, $rho, $factor) = (2, 1, 1);

while ($factor == 1) {

$rho *= 2;

my $fixed = $x;

for (0..$rho) {

$x = ( $x * $x + $constant ) % $n;

$factor = gcd(($x-$fixed), $n);

last if 1 < $factor;

}

}

$factor = find_factor($n, $constant+1) if $n == $factor;

$factor;

}

my @nth = (26828, 1e5, 2e5, 3e5, 4e5);

my($i, @blum);

while (++$i) {

push @blum, $i if is_blum $i;

last if $nth[-1] == scalar @blum;

}

say 'The first fifty Blum integers:';

say table 10, @blum[0..49];

printf "The %7sth Blum integer: %9s\n", comma($_), comma $blum[$_-1] for @nth;

</syntaxhighlight>

{{out}}

<pre>

The first fifty Blum integers:

21 33 57 69 77 93 129 133 141 161

177 201 209 213 217 237 249 253 301 309

321 329 341 381 393 413 417 437 453 469

473 489 497 501 517 537 553 573 581 589

597 633 649 669 681 713 717 721 737 749

The 26,828th Blum integer: 524,273

The 100,000th Blum integer: 2,075,217

The 200,000th Blum integer: 4,275,533

The 300,000th Blum integer: 6,521,629

The 400,000th Blum integer: 8,802,377</pre>