Python Program to Check for Semiprime Numbers
Determine if a Number is Semiprime with Python
This tutorial explains how to create a Python function to determine if a positive integer is a semiprime.
What is a semiprime number?
A semiprime number is a natural number that is the product of exactly two prime numbers. These prime factors can be the same, for example, 9 = 3 * 3.
**Code Implementation:pythondef isPrime(num): 'Efficiently checks if a number is prime.' if num < 2: return False for i in range(2, int(num0.5) + 1): if num % i == 0: return False return True
def isSemiprime(n): 'Determines if a number is semiprime.' prime_factors = [] for i in range(2, int(n**0.5) + 1): if n % i == 0: if isPrime(i): prime_factors.append(i) if isPrime(n // i) and i != n // i: prime_factors.append(n // i) return len(prime_factors) == 2
Test Casesassert isSemiprime(6) == Trueassert isSemiprime(9) == Trueassert isSemiprime(1) == Falseassert isSemiprime(7) == Falseassert isSemiprime(12) == False
Explanation:
-
isPrime(num)Function: - This function efficiently determines if a given numbernumis prime. - It first handles the case wherenumis less than 2 (not prime). - It then iterates from 2 up to the square root ofnum. We only need to check divisors up to the square root because any factor larger than the square root will have a corresponding factor smaller than the square root. - If a divisoriis found, the number is not prime, so it returnsFalse. - If no divisors are found within the loop, the number is prime, and the function returnsTrue. -
isSemiprime(n)Function: - This function determines if a given numbernis semiprime. - It initializes an empty listprime_factorsto store the prime factors found. - Similar toisPrime, it iterates from 2 up to the square root ofn. - Ifiis a factor ofn, it checks ifiis prime using theisPrimefunction. If so, it appendsito theprime_factorslist. - It then checks ifn // i(the other factor ofn) is prime and that it's not equal toi(to avoid duplicates when both factors are the same). If both conditions are met, it appendsn // ito theprime_factorslist. - Finally, it checks if the length of theprime_factorslist is exactly 2. If so, it returnsTrueindicating thatnis a semiprime; otherwise, it returnsFalse.
Key Points and Optimizations:
- Efficiency: Both functions are optimized for efficiency. The
isPrimefunction iterates only up to the square root of the number, significantly reducing the number of checks required.- Clarity: The code includes clear and concise comments to enhance readability and understanding.- Test Cases: The included test cases demonstrate how to use the function and verify its correctness with various inputs.
This tutorial provides a clear and efficient way to determine if a number is semiprime in Python, making it suitable for beginners and those looking for optimized solutions.
原文地址: https://www.cveoy.top/t/topic/STL 著作权归作者所有。请勿转载和采集!