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.


extern crate primal;
 
fn isqrt(n: usize) -> usize {
    (n as f64).sqrt() as usize
}
 
fn is_semiprime(mut n: usize) -> bool {
    let root = isqrt(n) + 1;
    let primes1 = primal::Sieve::new(root);
    let mut count = 0;
 
    for i in primes1.primes_from(2).take_while(|&x| x < root) {
        while n % i == 0 {
            n /= i;
            count += 1;
        }
        if n == 1 {
            break;
        }
    }
 
    if n != 1 {
        count += 1;
    }
    count == 2
}
 
#[test]
fn test1() {
    assert_eq!((2..10).filter(|&n| is_semiprime(n)).count(), 3);
}
 
#[test]
fn test2() {
    assert_eq!((2..100).filter(|&n| is_semiprime(n)).count(), 34);
}
 
#[test]
fn test3() {
    assert_eq!((2..1_000).filter(|&n| is_semiprime(n)).count(), 299);
}
 
#[test]
fn test4() {
    assert_eq!((2..10_000).filter(|&n| is_semiprime(n)).count(), 2_625);
}
 
#[test]
fn test5() {
    assert_eq!((2..100_000).filter(|&n| is_semiprime(n)).count(), 23_378);
}
 
#[test]
fn test6() {
    assert_eq!((2..1_000_000).filter(|&n| is_semiprime(n)).count(), 210_035);
}