A semiprime number is an integer which can be expressed as a product of two distinct primes.
For example, is a semiprime number while isn’t.
Test if a natural number 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 is prime or not.
1. The primality test #
For testing the primality of , an integer, I’ll be checking for any factors of lying between to floor(. If such a single factor exists, then 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
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 , and exist for which .
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