Semiprime: Difference between revisions
→{{header|Perl 6}}: Add a second, more efficient example
(added aliases, and also links (URLs).) |
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Add a second, more efficient example) |
||
Line 1,088:
ok 19 - 13 19 5
ok 20 - 37 97 11 31</pre>
===More efficient example===
Here is a more verbose, but MUCH more efficient implementation. Demonstrating using it to find an infinite list of semiprimes and to check a range of integers to find the semiprimes.
{{works with|Rakudo|2017.02}}
<lang perl6>sub is-semiprime ( Int $n where * > 0 ) {
return False if $n.is-prime;
my $factor = find-factor( $n );
return True if $factor.is-prime && ( $n div $factor ).is-prime;
False;
}
sub find-factor ( Int $n, $constant = 1 ) {
my $x = 2;
my $rho = 1;
my $factor = 1;
while $factor == 1 {
$rho *= 2;
my $fixed = $x;
for ^$rho {
$x = ( $x * $x + $constant ) % $n;
$factor = ( $x - $fixed ) gcd $n;
last if 1 < $factor;
}
}
$factor = find-factor( $n, $constant + 1 ) if $n == $factor;
$factor;
}
INIT my $start = now;
# Infinite list of semiprimes
constant @semiprimes = 4, 6, 9, -> $p { ($p + 1 ... &is-semiprime).tail } ... *;
# Show the semiprimes < 100
say 'Semiprimes less than 100:';
say @semiprimes[^ @semiprimes.first: * > 100, :k ], "\n";
# Check individual integers, or in this case, a range
my $s = 2⁹⁷ - 1;
say "Is $_ semiprime?: ", is-semiprime( $_ ) for $s .. $s + 30;
say 'elapsed seconds: ', now - $start;
</lang>
{{out}}
<pre>Semiprimes less than 100:
(4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95)
Is 158456325028528675187087900671 semiprime?: True
Is 158456325028528675187087900672 semiprime?: False
Is 158456325028528675187087900673 semiprime?: False
Is 158456325028528675187087900674 semiprime?: False
Is 158456325028528675187087900675 semiprime?: False
Is 158456325028528675187087900676 semiprime?: False
Is 158456325028528675187087900677 semiprime?: False
Is 158456325028528675187087900678 semiprime?: False
Is 158456325028528675187087900679 semiprime?: False
Is 158456325028528675187087900680 semiprime?: False
Is 158456325028528675187087900681 semiprime?: False
Is 158456325028528675187087900682 semiprime?: False
Is 158456325028528675187087900683 semiprime?: False
Is 158456325028528675187087900684 semiprime?: False
Is 158456325028528675187087900685 semiprime?: False
Is 158456325028528675187087900686 semiprime?: False
Is 158456325028528675187087900687 semiprime?: False
Is 158456325028528675187087900688 semiprime?: False
Is 158456325028528675187087900689 semiprime?: False
Is 158456325028528675187087900690 semiprime?: False
Is 158456325028528675187087900691 semiprime?: False
Is 158456325028528675187087900692 semiprime?: False
Is 158456325028528675187087900693 semiprime?: False
Is 158456325028528675187087900694 semiprime?: False
Is 158456325028528675187087900695 semiprime?: False
Is 158456325028528675187087900696 semiprime?: False
Is 158456325028528675187087900697 semiprime?: False
Is 158456325028528675187087900698 semiprime?: False
Is 158456325028528675187087900699 semiprime?: False
Is 158456325028528675187087900700 semiprime?: False
Is 158456325028528675187087900701 semiprime?: True
elapsed seconds: 0.0574433</pre>
=={{header|PicoLisp}}==
| |||