Semiprime

Semiprime
You are encouraged to solve this task according to the task description, using any language you may know.

Semiprime numbers are natural numbers that are products of exactly two (possibly equal) prime numbers. Example: 1679 = 23 × 73 (This particular number was chosen as the length of the Arecibo message).

Write a function determining whether a given number is semiprime.

Ada

This imports the package Prime_Numbers from Prime decomposition#Ada.

<lang ada>with Prime_Numbers, Ada.Text_IO;

procedure Test_Semiprime is

  package Integer_Numbers is new 
    Prime_Numbers (Natural, 0, 1, 2); 
  use Integer_Numbers;
  

begin

  for N in 1 .. 100 loop
     if Decompose(N)'Length = 2 then -- N is a semiprime;

Ada.Text_IO.Put(Integer'Image(Integer(N)));

     end if;
  end loop;
  Ada.Text_IO.New_Line;
  for N in 1675 .. 1680 loop
     if Decompose(N)'Length = 2 then -- N is a semiprime;

Ada.Text_IO.Put(Integer'Image(Integer(N)));

     end if;
  end loop; 

end Test_Semiprime;</lang>

It outputs all semiprimes below 100 and all semiprimes between 1675 and 1680:

Output:

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
1678 1679 

Note that

1675 = 5 * 5 * 67, 
1676 = 2 * 2 * 419, 
1677 = 3 * 13 * 43,
1678 = 2 * 839,
1679 = 23 * 73,
1680 = 2 * 2 * 2 * 2 * 3 * 5 * 7,

so the result printed is actually correct.

AutoHotkey

Works with: AutoHotkey_L

<lang AutoHotkey>SetBatchLines -1 k := 1 loop, 100 { m := semiprime(k) StringSplit, m_m, m, - if ( m_m1 = "yes" ) list .= k . " " k++ } MsgBox % list list :=

===================================================================================================================================

k := 1675 loop, 5 { m := semiprime(k) StringSplit, m_m, m, - if ( m_m1 = "yes" ) list1 .= semiprime(k) . "`n" else list1 .= semiprime(k) . "`n" k++ } MsgBox % list1 list1 :=

===================================================================================================================================

The function==========================================================================================================================

semiprime(k) { start := floor(sqrt(k)) loop, % floor(sqrt(k)) - 1 { if ( mod(k, start) = 0 ) new .= floor(start) . "*" . floor(k//start) . "," start-- }

StringSplit, index, new, `,

if ( index0 = 2 ) { StringTrimRight, new, new, 1 StringSplit, 2_ind, new, * if (mod(2_ind2, 2_ind1) = 0) && ( 2_ind1 != 2_ind2 ) new := "N0- " . k . " - " . new else new := "yes- " . k . " - " . new } else new := "N0- " . k . " - " . new return new }

=================================================================================================================================================

esc::Exitapp</lang>

Output:

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
N0- 1675  -  25*67,5*335,
N0- 1676  -  4*419,2*838,
N0- 1677  -  39*43,13*129,3*559,
yes- 1678  -  2*839
yes- 1679  -  23*73

Bracmat

When Bracmat is asked to take the square (or any other) root of a number, it does so by first finding the number's prime factors. It can do that for numbers up to 2^32 or 2^64 (depending on compiler and processor). <lang bracmat>semiprime=

 m n a b

. 2^-64:?m

 & 2*!m:?n
 &   !arg^!m
   : (#%?a^!m*#%?b^!m|#%?a^!n&!a:?b)
 & (!a.!b);</lang>

Test with numbers < 2^63: <lang bracmat> 2^63:?u & whl

 ' ( -1+!u:>2:?u
   & ( semiprime$!u:?R&out$(!u ":" !R)
     | 
     )
   );</lang>

Output:

9223372036854775797 : (3.3074457345618258599)
9223372036854775777 : (584911.15768846947407)
9223372036854775771 : (19.485440633518672409)
9223372036854775753 : (266416229.34620158357)
9223372036854775727 : (11113.829962389710679)
9223372036854775717 : (59.156328339607708063)
9223372036854775715 : (5.1844674407370955143)
9223372036854775703 : (9648151.955973018753)
9223372036854775694 : (2.4611686018427387847)
9223372036854775691 : (37.249280325320399343)
9223372036854775687 : (1303.7078566413549329)
9223372036854775685 : (5.1844674407370955137)
9223372036854775673 : (175934777.52424950849)
9223372036854775634 : (2.4611686018427387817)
9223372036854775633 : (421741.21869754273013)
9223372036854775627 : (6277.1469391753521551)
9223372036854775609 : (172153.53576597775553)
9223372036854775601 : (1045692671.8820346831)
9223372036854775589 : (563.16382543582335303)
9223372036854775577 : (267017141.34542246997)
9223372036854775574 : (2.4611686018427387787)
9223372036854775571 : (1951.4727510013764621)
9223372036854775537 : (47.196241958230952671)
9223372036854775531 : (1677122561.5499521771)
9223372036854775522 : (2.4611686018427387761)
9223372036854775511 : (29305709.314729530579)
9223372036854775502 : (2.4611686018427387751)
9223372036854775489 : (9413717.979780041917)
9223372036854775474 : (2.4611686018427387737)
9223372036854775466 : (2.4611686018427387733)
9223372036854775461 : (3.3074457345618258487)
9223372036854775451 : (545369243.16912160257)
9223372036854775439 : (11380717.810438572267)
9223372036854775418 : (2.4611686018427387709)
9223372036854775411 : (1420967.6490912200533)
9223372036854775409 : (15060911.612404657119)
9223372036854775407 : (3.3074457345618258469)
9223372036854775402 : (2.4611686018427387701)
9223372036854775389 : (3.3074457345618258463)
9223372036854775385 : (5.1844674407370955077)
9223372036854775383 : (3.3074457345618258461)
9223372036854775381 : (683.13504205031998207)
9223372036854775379 : (43.214497024112901753)
9223372036854775357 : (17.542551296285575021)
9223372036854775355 : (5.1844674407370955071)
^CTerminate batch job (Y/N)? Y

C

<lang c>#include <stdio.h>

int semiprime(int n) { int p, f = 0; for (p = 2; f < 2 && p*p <= n; p++) while (0 == n % p) n /= p, f++;

return f + (n > 1) == 2; }

int main(void) { int i; for (i = 2; i < 100; i++) if (semiprime(i)) printf(" %d", i); putchar('\n');

return 0; }</lang>

Output:

 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

C++

<lang cpp>

1. include <iostream>

bool isSemiPrime( int c ) {

   int a = 2, b = 0;
   while( b < 3 && c != 1 )
   {

if( !( c % a ) ) { c /= a; b++; } else a++;

   }
   return b == 2;

} int main( int argc, char* argv[] ) {

   for( int x = 2; x < 100; x++ )

if( isSemiPrime( x ) ) std::cout << x << " ";

   return 0;

} </lang>

Output:

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 

Common Lisp

<lang lisp>(defun semiprimep (n &optional (a 2))

 (cond ((> a (isqrt n)) nil)
       ((zerop (rem n a)) (and (primep a) (primep (/ n a))))
       (t (semiprimep n (+ a 1)))))

(defun primep (n &optional (a 2))

 (cond ((> a (isqrt n)) t)
       ((zerop (rem n a)) nil)
       (t (primep n (+ a 1)))))</lang>

Example Usage:

CL-USER> (semiprimep 1234567)
T
CL-USER> (semiprimep 9876543)
NIL

D

Translation of: Go

<lang d>bool semiprime(long n) pure nothrow @safe @nogc {

   auto nf = 0;
   foreach (immutable i; 2 .. n + 1) {
       while (n % i == 0) {
           if (nf == 2)
               return false;
           nf++;
           n /= i;
       }
   }
   return nf == 2;

}

void main() {

   import std.stdio;

   foreach (immutable n; 1675 .. 1681)
       writeln(n, " -> ", n.semiprime);

}</lang>

Output:

1675 -> false
1676 -> false
1677 -> false
1678 -> true
1679 -> true
1680 -> false

DCL

Given a file primes.txt is the list of primes up to the sqrt(2^31-1), i.e. 46337; <lang DCL>$ p1 = f$integer( p1 ) $ if p1 .lt. 2 $ then $ write sys$output "out of range 2 thru 2^31-1" $ exit $ endif $ $ close /nolog primes $ on control_y then $ goto clean $ open primes primes.txt $ $ loop1: $ read /end_of_file = prime primes prime $ prime = f$integer( prime ) $ loop2: $ t = p1 / prime $ if t * prime .eq. p1 $ then $ if f$type( factorization ) .eqs. "" $ then $ factorization = f$string( prime ) $ else $ factorization = factorization + "*" + f$string( prime ) $ endif $ if t .eq. 1 then $ goto done $ p1 = t $ goto loop2 $ else $ goto loop1 $ endif $ prime: $ if f$type( factorization ) .eqs. "" $ then $ factorization = f$string( p1 ) $ else $ factorization = factorization + "*" + f$string( p1 ) $ endif $ done: $ show symbol factorization $ if f$locate( "*", factorization ) .eq. f$length( factorization ) $ then $ write sys$output "so, it is prime" $ else $ if f$element( 2, "*", factorization ) .eqs. "*" then $ write sys$output "so, it is semiprime" $ endif $ $ clean: $ close primes</lang>

Output:

$ @factor 6
  FACTORIZATION = "2*3"
so, it is semiprime
$ @factor 11
  FACTORIZATION = "11"
so, it is prime
$ @factor 2147483646
  FACTORIZATION = "2*3*3*7*11*31*151*331"

EchoLisp

<lang scheme> (lib 'math) (define (semi-prime? n)

  (= (length (prime-factors n)) 2))

(for ((i 100))

   (when (semi-prime? i) (write i)))

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

(lib 'bigint) (define N (* (random-prime 10000000) (random-prime 10000000)))

  → 6764578882969

(semi-prime? N)

   → #t

a pair n,n+1 of semi-primes

(prime-factors 100000000041)

   → (3 33333333347)

(prime-factors 100000000042)

   → (2 50000000021)

</lang>

Erlang

Another using prime factors from Prime_decomposition#Erlang :

<lang erlang> -module(factors). -export([factors/1,kthfactor/2]).

factors(N) ->

    factors(N,2,[]).

factors(1,_,Acc) -> Acc; factors(N,K,Acc) when N rem K == 0 ->

   factors(N div K,K, [K|Acc]);

factors(N,K,Acc) ->

   factors(N,K+1,Acc).

% is integer N factorable into M primes? kthfactor(N,M) ->

   case length(factors(N)) of M ->
     factors(N);
     _ ->
     false end.                      

</lang> {out}

17> factors:kthfactor(1679,2).
[73,23]
18> factors:kthfactor(1679,4).
false
23> FS = [{X,factors:kthfactor(X,2)} || X <- lists:seq(50,500), factors:kthfactor(X,2) =/= false]. 
[{51,[17,3]},
 {55,[11,5]},
 {57,[19,3]},
 {58,[29,2]},
 {62,[31,2]},
 {65,[13,5]},
 {69,[23,3]},
 {74,[37,2]},
 {77,[11,7]},
 {82,[41,2]},
 {85,[17,5]},
 {86,[43,2]},
 {87,[29,3]},
 {91,[13,7]},
 {93,[31,3]},
 {94,[47,2]},
 {95,[19,5]},
 {106,[53,2]},
 {111,[37,3]},
 {115,[23,5]},
 {118,[59,2]},
 {119,[17,7]},
 {121,"\v\v"},
 {122,[61,2]},
 {123,[41,3]},
 {129,[43|...]},
 {133,[...]},
 {134,...},
 {...}|...]

Note, there is some junk character data in the output since we 'usually' have to filter for char sequences (it's not a bug, it's a feature!).

ERRE

<lang> PROGRAM SEMIPRIME_NUMBER

!VAR I%

PROCEDURE SEMIPRIME(N%->RESULT%)

  LOCAL F%,P%
  P%=2
  LOOP
      EXIT IF NOT(F%<2 AND P%*P%<=N%)
      WHILE (N% MOD P%)=0 DO
           N%=N% DIV P%
           F%+=1
      END WHILE
      P%+=1
   END LOOP
   RESULT%=F%-(N%>1)=2

END PROCEDURE

BEGIN

   PRINT(CHR$(12);) !CLS
   FOR I%=2 TO 100 DO
        SEMIPRIME(I%->RESULT%)
        IF RESULT% THEN PRINT(I%;) END IF
   END FOR
   PRINT

END PROGRAM </lang> Output is the same of "C" version.

F#

<lang fsharp>let isSemiprime (n: int) =

   let rec loop currentN candidateFactor numberOfFactors =
       if numberOfFactors > 2 then numberOfFactors
       elif currentN = candidateFactor then numberOfFactors+1
       elif currentN % candidateFactor = 0 then loop (currentN/candidateFactor) candidateFactor (numberOfFactors+1)
       else loop currentN (candidateFactor+1) numberOfFactors
   if n < 2 then false else 2 = loop n 2 0

seq { 1 .. 100 } |> Seq.choose (fun n -> if isSemiprime n then Some(n) else None) |> Seq.toList |> printfn "%A"

seq { 1675 .. 1680 } |> Seq.choose (fun n -> if isSemiprime n then Some(n) else None) |> Seq.toList |> printfn "%A"</lang>

Output:

[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]
[1678; 1679]

Forth

<lang forth>: semiprime?

 0 swap dup 2 do
   begin dup i mod 0= while i / swap 1+ swap repeat
   over 1 > over i dup * < or if leave then
 loop 1 > abs + 2 =

test 100 2 do i semiprime? if i . then loop cr ;</lang>

Output:

test 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
 ok

Go

<lang go>package main

import "fmt"

func semiprime(n int) bool {

   nf := 0
   for i := 2; i <= n; i++ {
       for n%i == 0 {
           if nf == 2 {
               return false
           }
           nf++
           n /= i
       }
   }
   return nf == 2

}

func main() {

   for v := 1675; v <= 1680; v++ {
       fmt.Println(v, "->", semiprime(v))
   }

}</lang>

Output:

1675 -> false
1676 -> false
1677 -> false
1678 -> true
1679 -> true
1680 -> false

Haskell

Library: Data.Numbers.Primes

<lang Haskell>isSemiprime :: Int -> Bool isSemiprime n = (length factors) == 2 && (product factors) == n ||

               (length factors) == 1 && (head factors) ^ 2 == n
                   where factors = primeFactors n</lang>

Alternative (and faster) implementation using pattern matching: <lang Haskell>isSemiprime :: Int -> Bool isSemiprime n = case (primeFactors n) of

                  [f1, f2] -> f1 * f2 == n
                  otherwise -> False</lang>

Icon and Unicon

Works in both languages: <lang unicon>link "factors"

procedure main(A)

   every nf := semiprime(n := !A) do write(n," = ",nf[1]," * ",nf[2])

end

procedure semiprime(n) # Succeeds and produces the factors only if n is semiprime.

   return (2 = *(nf := factors(n)), nf)

end</lang>

Output:

->semiprime 1676 1677 1678 1679 1680
1678 = 2 * 839
1679 = 23 * 73
->

J

Implementation:

<lang J>isSemiPrime=: 2 = #@q: ::0:"0</lang>

Example use: find all semiprimes less than 100:

<lang J> I. isSemiPrime i.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</lang>

Description: factor the number and count the primes in the factorization, is it 2?

Java

Works with: Java version 1.5+

Inspired by: #Ada

Like the Ada example here, this borrows from Prime decomposition and shows the semiprimes below 100 and from 1675 to 1680. <lang java5>import java.math.BigInteger; import java.util.ArrayList; import java.util.List;

public class SemiPrime{ private static final BigInteger TWO = BigInteger.valueOf(2);

public static List<BigInteger> primeDecomp(BigInteger a){ // impossible for values lower than 2 if(a.compareTo(TWO) < 0){ return null; }

//quickly handle even values List<BigInteger> result = new ArrayList<BigInteger>(); while(a.and(BigInteger.ONE).equals(BigInteger.ZERO)){ a = a.shiftRight(1); result.add(TWO); }

//left with odd values if(!a.equals(BigInteger.ONE)){ BigInteger b = BigInteger.valueOf(3); while(b.compareTo(a) < 0){ if(b.isProbablePrime(10)){ BigInteger[] dr = a.divideAndRemainder(b); if(dr[1].equals(BigInteger.ZERO)){ result.add(b); a = dr[0]; } } b = b.add(TWO); } result.add(b); //b will always be prime here... } return result; }

public static boolean isSemi(BigInteger x){ List<BigInteger> decomp = primeDecomp(x); return decomp != null && decomp.size() == 2; }

public static void main(String[] args){ for(int i = 2; i <= 100; i++){ if(isSemi(BigInteger.valueOf(i))){ System.out.print(i + " "); } } System.out.println(); for(int i = 1675; i <= 1680; i++){ if(isSemi(BigInteger.valueOf(i))){ System.out.print(i + " "); } } } }</lang>

Output:

4 6 9 10 14 15 21 22 25 26 27 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 81 82 85 86 87 91 93 94 95 
1678 1679

Julia

(Uses the built-in factor function.) <lang julia>semiprime(n) = sum(values(factor(n))) == 2</lang>

Output:

julia> filter(semiprime, 1: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]

Maple

<lang Maple>SemiPrimes := proc( n )

   local fact;
   fact := numtheory:-divisors( n ) minus {1, n};
   if numelems( fact ) in {1,2} and not( member( 'false', isprime ~ ( fact ) ) ) then
       return n;
   else
       return NULL;
   end if;

end proc: { seq( SemiPrime( i ), i = 1..100 ) };</lang> Output: <lang Maple> { 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 } </lang>

Mathematica

<lang Mathematica>semiPrimeQ[n_Integer] := Module[{factors, numfactors},

 factors = FactorInteger[n] // Transpose;
 numfactors = factors2 // Total  ;
 numfactors == 2
 ]

</lang> Example use: find all semiprimes less than 100: <lang Mathematica>semiPrimeQ[#] & /@ Range[100]; Position[%, True] // Flatten</lang>

Output:

{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}

Objeck

Translation of: Go

<lang objeck> class SemiPrime {

 function : Main(args : String[]) ~ Nil {
   for(i := 0; i < 100; i+=1;) {
     if(SemiPrime(i)) {
       "{$i} "->Print();
     };
   };
   IO.Console->PrintLine();
 }
 
 function : native : SemiPrime(n : Int) ~ Bool {
   nf := 0;
   for(i := 2; i <= n; i+=1;) {
     while(n%i = 0) {
       if(nf = 2) {
         return false;
       };
       nf+=1;
       n /= i;
     };
   };
   
   return nf = 2;
 }

}</lang>

Output:

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

Oforth

<lang Oforth>func: semiprime(n) { | i |

  0 2 n sqrt asInteger for: i [ while(n i /mod swap 0 &=) [ ->n 1 + ] drop ]
  n 1 > ifTrue: [ 1 + ] 2 ==

}</lang>

Output:

100 seq filter(#semiprime) println
[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]

PARI/GP

<lang parigp>issemi(n)=bigomega(n)==2</lang>

A faster version might use trial division and primality testing: <lang parigp>issemi(n)={

 forprime(p=2,97,if(n%p==0, return(isprime(n/p))));
 if(isprime(n), return(0));
 bigomega(n)==2

};</lang>

To get faster, partial factorization can be used. At this time GP does not have access to meaningful partial factorization (though it can get it to some extent through flags on factorint), so this version is in PARI: <lang c>long issemiprime(GEN n) {

 if (typ(n) != t_INT)
   pari_err_TYPE("issemiprime", n);
 if (signe(n) <= 0)
   return 0;

 ulong nn = itou_or_0(n);
 if (nn)
   return uissemiprime(nn);

 pari_sp ltop = avma;
 if (!mpodd(n)) {
   long ret = mod4(n) && isprime(shifti(n, -1));
   avma = ltop;
   return ret;
 }

 long p;
 forprime_t primepointer;
 u_forprime_init(&primepointer, 3, 997);
 while ((p = u_forprime_next(&primepointer))) {
   if (dvdis(n, p)) {
     long ret = isprime(diviuexact(n, p));
     avma = ltop;
     return ret;
   }
 }

 if (isprime(n))
   return 0;

 if (DEBUGLEVEL > 3)
   pari_printf("issemi: Number is a composite with no small prime factors; using general factoring mechanisms.");

 GEN fac = Z_factor_until(n, shifti(n, -1));	/* Find a nontrivial factor -- returns just the factored part */
 GEN expo = gel(fac, 2);
 GEN pr = gel(fac, 1);
 long len = glength(expo);
 if (len > 2) {
   avma = ltop;
   return 0;
 }
 if (len == 2) {
   if (cmpis(gel(expo, 1), 1) > 0 || cmpis(gel(expo, 2), 1) > 0) {
     avma = ltop;
     return 0;
   }
   GEN P = gel(pr, 1);
   GEN Q = gel(pr, 2);
   long ret = isprime(P) && isprime(Q) && equalii(mulii(P, Q), n);
   avma = ltop;
   return ret;
 }
 if (len == 1) {
   long e = itos(gel(expo, 1));
   if (e == 2) {
     GEN P = gel(pr, 1);
     long ret = isprime(P) && equalii(sqri(P), n);
     avma = ltop;
     return ret;
   } else if (e > 2) {
     avma = ltop;
     return 0;
   }
   GEN P = gel(pr, 1);
   long ret = isprime(P) && isprime(diviiexact(n, P));
   avma = ltop;
   return ret;
 }

 pari_err_BUG(pari_sprintf("Z_factor_until returned an unexpected value %Ps at n = %Ps, exiting...", fac, n));
 avma = ltop;
 return 0; /* never used */

}</lang>

Pascal

Library: primTrial

Works with: Free Pascal

<lang pascal>program SemiPrime; {$IFDEF FPC}

 {$Mode objfpc}// compiler switch to use result

{$ELSE}

 {$APPTYPE CONSOLE} // for Delphi

{$ENDIF} uses

 primTrial;

function isSemiprime(n: longWord;doWrite:boolean): boolean; var

 fac1 : LongWord;

begin

 //a simple isAlmostPrime(n,2) would do without output;
 fac1 := SmallFactor(n);
 IF fac1 < n then
 Begin
   n := n div fac1;
   result := SmallFactor(n) = n;
   if result AND doWrite then
     write(fac1:10,'*',n:11)
 end
 else
   result := false;

end; var

 i,k : longWord;

BEGIN

 For i := 2 to 97 do
   IF isSemiPrime(i,false) then
     write(i:3);
 writeln;
 //test for big numbers
 k := 4000*1000*1000;
 i := k-100;
 repeat
   IF isSemiPrime(i,true) then
     writeln(' = ',i:10);
   inc(i);
 until i> k;

END.</lang>

output

 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

        71*   56338027 = 3999999917
     42307*      94547 = 3999999929
        59*   67796609 = 3999999931
         5*  799999987 = 3999999935
         2* 1999999973 = 3999999946
        11*  363636359 = 3999999949
       103*   38834951 = 3999999953
     12007*     333139 = 3999999973
         7*  571428569 = 3999999983
         5*  799999999 = 3999999995

Perl

Library: ntheory

factor in scalar context gives the number of factors (like bigomega in Pari/GP and PrimeOmega in Mathematica). <lang perl>use ntheory "factor"; print join(" ", grep { scalar factor($_) == 2 } 1..100),"\n"; print join(" ", grep { scalar factor($_) == 2 } 1675..1681),"\n"; print join(" ", grep { scalar factor($_) == 2 } (2,4,99,100,1679,5040,32768,1234567,9876543,900660121)),"\n";</lang>

Output:

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
1678 1679 1681
4 1679 1234567 900660121

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>use ntheory qw/factor is_prime trial_factor/; sub issemi {

 my $n = shift;
 if ((my @p = trial_factor($n,500)) > 1) {
   return 0 if @p > 2;
   return !!is_prime($p[1]) if @p == 2;
 }
 2 == factor($n);

}</lang>

Perl 6

Here is a naive, grossly inefficient implementation. <lang perl6>sub is-semiprime (Int $n --> Bool) {

   not $n.is-prime and
       .is-prime given 
       $n div first $n %% *,
           grep &is-prime, 2 .. *;

}

use Test; my @primes = grep &is-prime, 2 .. 100; for ^5 {

   nok is-semiprime([*] my @f1 = @primes.roll(1)), ~@f1;
   ok  is-semiprime([*] my @f2 = @primes.roll(2)), ~@f2;
   nok is-semiprime([*] my @f3 = @primes.roll(3)), ~@f3;
   nok is-semiprime([*] my @f4 = @primes.roll(4)), ~@f4;

}</lang>

Output:

ok 1 - 17
ok 2 - 47 23
ok 3 - 23 37 41
ok 4 - 53 37 67 47
ok 5 - 5
ok 6 - 73 43
ok 7 - 13 53 71
ok 8 - 7 79 37 71
ok 9 - 41
ok 10 - 71 37
ok 11 - 37 53 43
ok 12 - 3 2 47 67
ok 13 - 17
ok 14 - 41 61
ok 15 - 71 31 79
ok 16 - 97 17 73 17
ok 17 - 61
ok 18 - 73 47
ok 19 - 13 19 5
ok 20 - 37 97 11 31

PicoLisp

<lang PicoLisp>(de factor (N)

  (make
     (let
        (D 2
           L (1 2 2 . (4 2 4 2 4 6 2 6 .))
           M (sqrt N) )
        (while (>= M D)
           (if (=0 (% N D))
              (setq M 
                 (sqrt (setq N (/ N (link D)))) )
              (inc 'D (pop 'L)) ) )
        (link N) ) ) )

(println

  (filter
     '((X) 
        (let L (factor X)
           (and (cdr L) (not (cddr L))) ) )
     (conc (range 1 100) (range 1675 1680)) ) )
     

(bye)</lang>

Output:

(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 1678 1679)

PL/I

<lang pli>*process source attributes xref nest or(!);

/*--------------------------------------------------------------------
* 22.02.2014 Walter Pachl using the is_prime code from
*                         PL/I 'prime decomposition'
* 23.02.  WP start test for second prime with 2 or first prime found
*-------------------------------------------------------------------*/
spb: Proc options(main);
Dcl a(10) Bin Fixed(31)
         Init(900660121,2,4,1679,1234567,32768,99,9876543,100,5040);
Dcl (x,n,nf,i,j) Bin Fixed(31) Init(0);
Dcl f(3) Bin Fixed(31);
Dcl txt Char(30) Var;
Dcl bit Bit(1);
Do i=1 To hbound(a);
  bit=is_semiprime(a(i));
  Select(nf);
    When(0,1) txt=' is prime';
    When(2)   txt=' is     semiprime '!!factors(a(i));
    Otherwise txt=' is NOT semiprime '!!factors(a(i));
    End;
  Put Edit(a(i),bit,txt)(Skip,f(10),x(1),b(1),a);
  End;

is_semiprime: Proc(x) Returns(bit(1));
/*--------------------------------------------------------------------
* Returns '1'b if x is semiprime, '0'b otherwise
* in addition
* it sets f(1) and f(2) to the first (or only) prime factor(s)
*-------------------------------------------------------------------*/
  Dcl x Bin Fixed(31);
  nf=0;
  f=0;
  x=a(i);
  n=x;
  f(1)=2;
loop:
  Do While(nf<=2 & n>1);
    If is_prime(n) Then Do;
      Call mem(n);
      Leave loop;
      End;
    Else Do;
loop2:
      Do j=f(1) By 1 While(j*j<=n);
        If is_prime(j)&mod(n,j)=0 Then Do;
          Call mem(j);
          n=n/j;
          Leave loop2;
          End;
        End;
      End;
    End;
  Return(nf=2);
End;

is_prime: Proc(n) Returns(bit(1));
Dcl n Bin Fixed(31);
Dcl i Bin Fixed(31);
  If n < 2 Then Return('0'b);
  If n = 2 Then Return('1'b);
  If mod(n,2)=0 Then Return('0'b);
  Do i = 3 by 2 While(i*i<=n);
    If mod(n,i)=0 Then Return('0'b);
    End;
  Return('1'b);
End is_prime;

mem: Proc(x);
Dcl x Bin Fixed(31);
  nf+=1;
  f(nf)=x;
End;

factors: Proc(x) Returns(Char(150) Var);
Dcl x Bin Fixed(31);
Dcl (res,net) Char(150) Var Init();
Dcl (i,f3) Bin Fixed(31);
res=f(1)!!'*'!!f(2);
f3=x/(f(1)*f(2));
If f3>1 Then
  res=res!!'*'!!f3;
Do i=1 To length(res);
  If substr(res,i,1)>' ' Then
    net=net!!substr(res,i,1);
  End;
Return(net);
End;

End spb;

</lang> Output:

 900660121 1 is     semiprime 30011*30011
         2 0 is prime
         4 1 is     semiprime 2*2
      1679 1 is     semiprime 23*73
   1234567 1 is     semiprime 127*9721
     32768 0 is NOT semiprime 2*2*8192
        99 0 is NOT semiprime 3*3*11
   9876543 0 is NOT semiprime 3*227*14503
       100 0 is NOT semiprime 2*2*25
      5040 0 is NOT semiprime 2*2*1260

Python

This imports Prime decomposition#Python <lang python>from prime_decomposition import decompose

def semiprime(n):

   d = decompose(n)
   try:
       return next(d) * next(d) == n
   except:
       return False</lang>

Output:

From Idle: <lang python>>>> semiprime(1679) True >>> [n for n in range(1,101) if semiprime(n)] [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] >>> </lang>

Racket

The first implementation considers all pairs of factors multiplying up to the given number and determines if any of them is a pair of primes. <lang Racket>#lang racket (require math)

(define (pair-factorize n)

 "Return all two-number factorizations of a number"
 (let ([up-limit (integer-sqrt n)])
   (map (λ (x) (list x (/ n x)))

(filter (λ (x) (<= x up-limit)) (divisors n)))))

(define (semiprime n)

 "Determine if a number is semiprime i.e. a product of two primes.

Check if any pair of complete factors consists of primes."

 (for/or ((pair (pair-factorize n)))
   (for/and ((el pair))
     (prime? el))))</lang>

The alternative implementation operates directly on the list of prime factors and their multiplicities. It is approximately 1.6 times faster than the first one (according to some simple tests of mine). <lang Racket>#lang racket (require math)

(define (semiprime n)

 "Alternative implementation.

Check if there are two prime factors whose product is the argument or if there is a single prime factor whose square is the argument"

 (let ([prime-factors (factorize n)])
   (or (and (= (length prime-factors) 1)

(= (expt (caar prime-factors) (cadar prime-factors)) n)) (and (= (length prime-factors) 2) (= (foldl (λ (x y) (* (car x) y)) 1 prime-factors) n)))))</lang>

REXX

version 1

<lang rexx>/* REXX ---------------------------------------------------------------

• 20.02.2014 Walter Pachl relying on 'prime decomposition'
• 21.02.2014 WP Clarification: I copied the algorithm created by
• Gerard Schildberger under the task referred to above
• 21.02.2014 WP Make sure that factr is not called illegally
• --------------------------------------------------------------------*/

Call test 4 Call test 9 Call test 10 Call test 12 Call test 1679 Exit

test: Parse Arg z If is_semiprime(z) Then Say z 'is semiprime' fl

                  Else Say z 'is NOT semiprime' fl

Return

is_semiprime:

 Parse Arg z
 If z<1 | datatype(z,'W')=0 Then Do
   Say 'Argument ('z') must be a natural number (1, 2, 3, ...)'
   fl=
   End
 Else
   fl=factr(z)
 Return words(fl)=2    

/*----------------------------------FACTR subroutine-----------------*/ factr: procedure; parse arg x 1 z,list /*sets X&Z to arg1, LIST=. */ if x==1 then return /*handle the special case of X=1.*/ j=2; call .factr /*factor for the only even prime.*/ j=3; call .factr /*factor for the 1st odd prime.*/ j=5; call .factr /*factor for the 2nd odd prime.*/ j=7; call .factr /*factor for the 3rd odd prime.*/ j=11; call .factr /*factor for the 4th odd prime.*/ j=13; call .factr /*factor for the 5th odd prime.*/ j=17; call .factr /*factor for the 6th odd prime.*/

                                   /* [?]   could be optimized more.*/
                                   /* [?]   J in loop starts at 17+2*/
    do y=0  by 2;     j=j+2+y//4   /*insure J isn't divisible by 3. */
    if right(j,1)==5  then iterate /*fast check for divisible by 5. */
    if j*j>z          then leave   /*are we higher than the v of Z ?*/
    if j>Z            then leave   /*are we higher than value of Z ?*/
    call .factr                    /*invoke .FACTR for some factors.*/
    end   /*y*/                    /* [?]  only tests up to the v X.*/
                                   /* [?]  LIST has a leading blank.*/

if z==1 then return list /*if residual=unity, don't append*/

             return list z         /*return list,  append residual. */

/*-------------------------------.FACTR internal subroutine----------*/ .factr: do while z//j==0 /*keep dividing until we can't. */

        list=list j                /*add number to the list  (J).   */
        z=z%j                      /*% (percent)  is integer divide.*/
        end   /*while z··· */      /*  //   ?---remainder integer ÷.*/

return /*finished, now return to invoker*/</lang> Output

4 is semiprime  2 2
9 is semiprime  3 3
10 is semiprime  2 5
12 is NOT semiprime  2 2 3
1679 is semiprime  23 73

version 2

The method used is to examine numbers, skipping primes.

If it's composite (the 1^st factor is prime), then check if the 2^nd factor is prime.   If so, the number is a semiprime.

The   isPrime   function could be optimized by utilizing an integer square root function instead of testing if   j*j>x   for every divisor. <lang rexx>/*REXX program determines if any number (or a range) is/are semiprime. */ parse arg bot top . /*obtain optional numbers from the C.L.*/ if bot==|bot=="," then bot=random() /*None given? User wants us to guess.*/ if top==|top=="," then top=bot /*maybe define a range of numbers. */ w=max(length(bot), length(top)) /*obtain the maximum width of numbers. */ numeric digits max(9,w) /*ensure there're enough decimal digits*/

            do n=bot  to top          /*show results for a range of numbers. */
            if isSemiPrime(n)  then say right(n,w)      "    is semiprime."
                               else say right(n,w)      " isn't semiprime."
            end   /*n*/

exit /*stick a fork in it, we're all done. */ /*────────────────────────────────────────────────────────────────────────────*/ isPrime: procedure; parse arg x; if x<2 then return 0 /*number too low*/ if wordpos(x, '2 3 5 7 11 13 17 19 23')\==0 then return 1 /*it's low prime*/ if x//2==0 then return 0; if x//3==0 then return 0 /*÷ by 2;÷ by 3?*/

 do j=5  by 6  until j*j>x;  if x//j==0      then return 0   /*not a prime.  */
                             if x//(j+2)==0  then return 0   /* "  "   "     */
 end   /*j*/

return 1 /*indicate that X is a prime number. */ /*────────────────────────────────────────────────────────────────────────────*/ isSemiPrime: procedure; parse arg x; if \datatype(x,'W') | x<4 then return 0 x=x/1

                 do i=2 for 2; if x//i==0  then  if isPrime(x%i)  then return 1
                                                                  else return 0
                 end   /*i*/
                                                                  /*    ___  */
 do   j=5  by 6;         if j*j>x    then  return 0               /* > √ x ? */
   do k=j  by 2  for 2;  if x//k==0  then  if isPrime(x%k)  then return 1
                                                            else return 0
   end   /*k*/                        /* [↑]  see if 2nd factor is prime or ¬*/
 end     /*j*/                        /* [↑]  never ÷ by J if J is mult. of 3*/</lang>

output   when the input is:   -1   106

 -1  isn't semiprime.
  0  isn't semiprime.
  1  isn't semiprime.
  2  isn't semiprime.
  3  isn't semiprime.
  4     is semiprime.
  5  isn't semiprime.
  6     is semiprime.
  7  isn't semiprime.
  8  isn't semiprime.
  9     is semiprime.
 10     is semiprime.
 11  isn't semiprime.
 12  isn't semiprime.
 13  isn't semiprime.
 14     is semiprime.
 15     is semiprime.
 16  isn't semiprime.
 17  isn't semiprime.
 18  isn't semiprime.
 19  isn't semiprime.
 20  isn't semiprime.
 21     is semiprime.
 22     is semiprime.
 23  isn't semiprime.
 24  isn't semiprime.
 25     is semiprime.
 26     is semiprime.
 27  isn't semiprime.
 28  isn't semiprime.
 29  isn't semiprime.
 30  isn't semiprime.
 31  isn't semiprime.
 32  isn't semiprime.
 33     is semiprime.
 34     is semiprime.
 35     is semiprime.
 36  isn't semiprime.
 37  isn't semiprime.
 38     is semiprime.
 39     is semiprime.
 40  isn't semiprime.
 41  isn't semiprime.
 42  isn't semiprime.
 43  isn't semiprime.
 44  isn't semiprime.
 45  isn't semiprime.
 46     is semiprime.
 47  isn't semiprime.
 48  isn't semiprime.
 49     is semiprime.
 50  isn't semiprime.
 51     is semiprime.
 52  isn't semiprime.
 53  isn't semiprime.
 54  isn't semiprime.
 55     is semiprime.
 56  isn't semiprime.
 57     is semiprime.
 58     is semiprime.
 59  isn't semiprime.
 60  isn't semiprime.
 61  isn't semiprime.
 62     is semiprime.
 63  isn't semiprime.
 64  isn't semiprime.
 65     is semiprime.
 66  isn't semiprime.
 67  isn't semiprime.
 68  isn't semiprime.
 69     is semiprime.
 70  isn't semiprime.
 71  isn't semiprime.
 72  isn't semiprime.
 73  isn't semiprime.
 74     is semiprime.
 75  isn't semiprime.
 76  isn't semiprime.
 77     is semiprime.
 78  isn't semiprime.
 79  isn't semiprime.
 80  isn't semiprime.
 81  isn't semiprime.
 82     is semiprime.
 83  isn't semiprime.
 84  isn't semiprime.
 85     is semiprime.
 86     is semiprime.
 87     is semiprime.
 88  isn't semiprime.
 89  isn't semiprime.
 90  isn't semiprime.
 91     is semiprime.
 92  isn't semiprime.
 93     is semiprime.
 94     is semiprime.
 95     is semiprime.
 96  isn't semiprime.
 97  isn't semiprime.
 98  isn't semiprime.
 99  isn't semiprime.
100  isn't semiprime.
101  isn't semiprime.
102  isn't semiprime.
103  isn't semiprime.
104  isn't semiprime.
105  isn't semiprime.
106     is semiprime.

output   when the input is:   99888111555   99888111600

99888111555  isn't semiprime.
99888111556  isn't semiprime.
99888111557  isn't semiprime.
99888111558  isn't semiprime.
99888111559  isn't semiprime.
99888111560  isn't semiprime.
99888111561  isn't semiprime.
99888111562  isn't semiprime.
99888111563     is semiprime.
99888111564  isn't semiprime.
99888111565  isn't semiprime.
99888111566     is semiprime.
99888111567  isn't semiprime.
99888111568  isn't semiprime.
99888111569     is semiprime.
99888111570  isn't semiprime.
99888111571  isn't semiprime.
99888111572  isn't semiprime.
99888111573  isn't semiprime.
99888111574     is semiprime.
99888111575  isn't semiprime.
99888111576  isn't semiprime.
99888111577  isn't semiprime.
99888111578     is semiprime.
99888111579  isn't semiprime.
99888111580  isn't semiprime.
99888111581  isn't semiprime.
99888111582  isn't semiprime.
99888111583  isn't semiprime.
99888111584  isn't semiprime.
99888111585  isn't semiprime.
99888111586  isn't semiprime.
99888111587  isn't semiprime.
99888111588  isn't semiprime.
99888111589  isn't semiprime.
99888111590  isn't semiprime.
99888111591     is semiprime.
99888111592  isn't semiprime.
99888111593     is semiprime.
99888111594  isn't semiprime.
99888111595  isn't semiprime.
99888111596  isn't semiprime.
99888111597  isn't semiprime.
99888111598  isn't semiprime.
99888111599  isn't semiprime.
99888111600  isn't semiprime.

Ruby

<lang ruby>require 'prime'

1. 75.prime_division # Returns the factorization.75 divides by 3 once and by 5 twice => [[3, 1], [5, 2]]

class Integer

 def semi_prime?
   prime_division.map( &:last ).inject( &:+ ) == 2
 end

end

p 1679.semi_prime? # true p ( 1..100 ).select( &:semi_prime? )

1. [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]

</lang>

Scala

Works with: Scala 2.9.1

<lang Scala>object Semiprime extends App {

 def isSP(n: Int): Boolean = {
   var nf: Int = 0
   var l = n
   for (i <- 2 to l/2) {
     while (l % i == 0) {
       if (nf == 2) return false
       nf +=1
       l /= i 
     }
   }
   nf == 2
 }

 (2 to 100) filter {isSP(_) == true} foreach {i => print("%d ".format(i))}
 println
 1675 to 1681 foreach {i => println(i+" -> "+isSP(i))}
 

}</lang>

Output:

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 
1675 -> false
1676 -> false
1677 -> false
1678 -> true
1679 -> true
1680 -> false
1681 -> true

Seed7

<lang seed7>$ include "seed7_05.s7i";

const func boolean: semiPrime (in var integer: n) is func

 result
   var boolean: isSemiPrime is TRUE;
 local
   var integer: p is 2;
   var integer: f is 0;
 begin
   while f < 2 and p**2 <= n do
     while n rem p = 0 do
       n := n div p;
       incr(f);
     end while;
     incr(p);
   end while;
   isSemiPrime := f + ord(n > 1) = 2;
 end func;

const proc: main is func

 local
   var integer: v is 0;
 begin
   for v range 1675 to 1680 do
     writeln(v <& " -> " <& semiPrime(v));
   end for;
 end func;</lang>

Output:

1675 -> FALSE                                                                                                                                                   
1676 -> FALSE                                                                                                                                                   
1677 -> FALSE                                                                                                                                                   
1678 -> TRUE                                                                                                                                                    
1679 -> TRUE                                                                                                                                                    
1680 -> FALSE

Sidef

<lang ruby>require 'ntheory';

func is_semiprime(n) {

   static nt = %S'ntheory';
   if (var p = [nt.trial_factor(n, 500)]) {
       return false if (p.len > 2);
       return !!nt.is_prime(p[1]) if (p.len == 2);
 }
 [nt.factor(n)].len == 2;

}

say [2,4,99,100,1679,32768,1234567,9876543,900660121].grep{ is_semiprime(_) }</lang>

Output:

[4, 1679, 1234567, 900660121]

Swift

<lang swift>import Foundation

func primes(n: Int) -> AnyGenerator<Int> {

 var (seive, i) = ([Int](0..<n), 1)
 let lim = Int(sqrt(Double(n)))
 
 return anyGenerator {
   while ++i < n {
     if seive[i] != 0 {
       if i <= lim {
         for notPrime in stride(from: i*i, to: n, by: i) {
           seive[notPrime] = 0
         }
       }
       return i
     }
   }
   return nil
 }

}

func isSemiPrime(n: Int) -> Bool {

 let g = primes(n)
 while let first = g.next() {
   if n % first == 0 {
     if first * first == n {
       return true
     } else {
       while let second = g.next() {
         if first * second == n { return true }
       }
     }
   }
 }
 return false

}</lang>

Tcl

Library: Tcllib (Package: math::numtheory)

<lang tcl>package require math::numtheory

proc isSemiprime n {

   if {!($n & 1)} {

return [::math::numtheory::isprime [expr {$n >> 1}]]

   }
   for {set i 3} {$i*$i < $n} {incr i 2} {

if {$n / $i * $i != $n && [::math::numtheory::isprime $i]} { if {[::math::numtheory::isprime [expr {$n/$i}]]} { return 1 } }

   }
   return 0

}

for {set n 1675} {$n <= 1680} {incr n} {

   puts -nonewline "$n is ... "
   if {[isSemiprime $n]} {

puts "a semiprime"

   } else {

puts "NOT a semiprime"

   }

}</lang>

Output:

1675 is ... a semiprime
1676 is ... NOT a semiprime
1677 is ... a semiprime
1678 is ... a semiprime
1679 is ... a semiprime
1680 is ... NOT a semiprime

zkl

Translation of: C

<lang zkl>fcn semiprime(n){

  reg f = 0;
  p:=2; while(f < 2 and p*p <= n){
     while(0 == n % p){ n /= p; f+=1; }
     p+=1;
  }
  return(f + (n > 1) == 2);

}</lang>

Output:

[1675 .. 1681].filter(semiprime).println();
L(1678,1679,1681)