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.

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>

Perl 6

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

   return False if $n.is-prime;
   return .is-prime given 
       $n div first $n %% *,
           grep &is-prime, 2 .. *;

}

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

   ok not is-semiprime([*] my @f1 = @primes.roll(1)), ~@f1;
   ok     is-semiprime([*] my @f2 = @primes.roll(2)), ~@f2;
   ok not is-semiprime([*] my @f3 = @primes.roll(3)), ~@f3;
   ok not 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

Python

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

def semiprime(n):

   d = decompose(n)
   try:
       return d.next() * d.next() == 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
• --------------------------------------------------------------------*/

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

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

             Else Say z 'is NOT semiprime' fl

Return

isprime:

 Parse Arg z
 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

<lang rexx>/*REXX program determines if any number (or a range) is/are semiprime.*/ parse arg bot top . /*obtain #s from the command line*/ if bot== then bot=random() /*so, the user wants us to guess.*/ if top== then top=bot /*maybe define a range of numbers*/ w=max(length(bot), length(top)) /*get maximum width of numbers. */ if w>digits() then numeric digits w /*is there enough digits ? */

            do n=bot  to top          /*show results for a range of #s.*/
            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 done.*/ /*──────────────────────────────────ISPRIME subroutine──────────────────*/ isPrime: procedure; parse arg x; if x<2 then return 0 if wordpos(x,'2 3 5 7')\==0 then return 1 /*handle some special cases*/

 do i=2  for 2;  if x//i==0  then return 0;  end  /*i*/    /*÷ by 2 & 3*/
 do j=5  by 6  until j*j>x;  if x//j==0      then return 0 /*¬ a prime#*/
                             if x//(j+2)==0  then return 0 /*¬ a prime#*/
 end   /*j*/

return 1 /*X is a prime number, for sure.*/ /*──────────────────────────────────ISSEMIPRIME subroutine──────────────*/ isSemiPrime: procedure; arg x; if \datatype(x,'W') | x<4 then return 0 x=x/1 /*normalize the X number. */

           do i=2 for 2; if x//i==0  then  if isPrime(x%i)  then return 1
                                                            else return 0
           end     /*i*/              /* [↑]  divides by two and three.*/
 do j=5  by  6;          if j*j>x    then  return 0         /*÷ by #s. */
   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 # divisible by 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.

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>