Semiprime numbers are natural numbers that are products of exactly two (possibly equal) prime numbers.


Semiprimes   are also known as:

   semi-primes
   biprimes
   bi-primes
    2-almost    primes
   or simply:    P2  


Example
 
   1679  =  23 × 73  

(This particular number was chosen as the length of the Arecibo message).



Task

Write a function determining whether a given number is semiprime.



See also

 The Wikipedia article:  semiprime.
 The Wikipedia article:  almost prime.
 The OEIS sequence:  A001358: semiprimes  which has a shorter definition: the product of two primes.


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