Enter, semiprime numbers


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

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

Test if a natural number nn is semiprime or not.


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

1. The primality test

For testing the primality of kk, an integer, I’ll be checking for any factors of kk lying between 22 to floor(k)\sqrt{k}). If such a single factor exists, then kk 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 nn, ii and jj exist for which i×j=ni \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