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:

  1. isPrime(num) Function: - This function efficiently determines if a given number num is prime. - It first handles the case where num is less than 2 (not prime). - It then iterates from 2 up to the square root of num. 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 divisor i is found, the number is not prime, so it returns False. - If no divisors are found within the loop, the number is prime, and the function returns True.

  2. isSemiprime(n) Function: - This function determines if a given number n is semiprime. - It initializes an empty list prime_factors to store the prime factors found. - Similar to isPrime, it iterates from 2 up to the square root of n. - If i is a factor of n, it checks if i is prime using the isPrime function. If so, it appends i to the prime_factors list. - It then checks if n // i (the other factor of n) is prime and that it's not equal to i (to avoid duplicates when both factors are the same). If both conditions are met, it appends n // i to the prime_factors list. - Finally, it checks if the length of the prime_factors list is exactly 2. If so, it returns True indicating that n is a semiprime; otherwise, it returns False.

Key Points and Optimizations:

  • Efficiency: Both functions are optimized for efficiency. The isPrime function 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.

Python Program to Check for Semiprime Numbers

原文地址: https://www.cveoy.top/t/topic/STL 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录