Semiprime

Semiprime numbers are natural numbers that are products of exactly two (possibly equal) prime_number. 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.

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>