Enter, semiprime numbers

competitive python nptel

Question #

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.

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

Related



Comments

Leave a reply