Enter, semiprime numbers

Question #

A semiprime number is an integer which can be expressed as a product of two distinct primes.

For example, $15 = 3 \times 5$ is a semiprime number while $9 = 3 \times 3$ isn’t.

Test if a natural number $n$ is semiprime or not.

Solution #

If we’re planning to approach this problem, we should start from the ground up, i.e. by starting with check if an integer $n$ is prime or not.

1. The primality test #

For testing the primality of $k$, an integer, I’ll be checking for any factors of $k$ lying between $2$ to floor($\sqrt{k})$. If such a single factor exists, then $k$ isn’t a prime and vice versa. Refer to this if you’re curious about the proof.
Writing this in code, we get:

def isPrime(k):
	for i in range(2, int(k**.5)+1):
		if k % i == 0:
			return False
	return True

Using next(), we can minify this snippet to get:

isPrime = next((i for i in range(2, int(k**.5)+1) if k%i == 0), -1) == -1

2. Testing for semiprimes #

For this test, we have to check if two prime factors of $n$, $i$ and $j$ exist for which $i \times j = n$.
In code, this can be written as:

def isSemiPrime(n):
	for i in range(2, n):
		if(n%i == 0 and isPrime(i) and isPrime(n/i)):
			return True
	return False

and hence we end up with our one-liner:

isSemiPrime = next((k for k in range(2, n) if n%k == 0 and isPrime(k) and isPrime(n/k)), -1) != -1