Semiprime: Difference between revisions

Content added Content deleted

Inline

@@ Line 528: / Line 528: @@
 =={{header|Perl}}==
+{{libheader|ntheory}}
 <tt>factor</tt> in scalar context gives the number of factors (like <tt>bigomega</tt> in Pari/GP and <tt>PrimeOmega</tt> in Mathematica).
-<lang perl>use Math::Prime::Util "factor";
+<lang perl>use ntheory "factor";
 print join(" ", grep { scalar factor($_) == 2 } 1..100),"\n";
 print join(" ", grep { scalar factor($_) == 2 } 1675..1681),"\n";
@@ Line 538: / Line 539: @@
 1679 1234567 900660121</pre>
-Following Pari/GP's example, for inputs over 10^10 or so, we can save some time by using trial division first:
+Following Pari/GP's example, for inputs over 10^10 or so, we can save some time by looking for small factors first:
-<lang perl>my @_small_primes = @{primes(100)};
+<lang perl>use ntheory qw/factor is_prime trial_factor/;
 sub issemi {
   my $n = shift;
-  for my $p (@_small_primes) { return !!is_prime($n/$p) unless $n % $p; }
+  if ((my @p = trial_factor($n,500)) > 1) {
+    return 0 if @p > 2;
+    return !!is_prime($p[1]) if @p == 2;
+  }
 == factor($n);
 }</lang>