How to use Python to implement the prime number judgment algorithm?

How to use Python to implement the prime number judgment algorithm?

Prime numbers refer to positive integers that can only be divisible by 1 and itself, such as 2, 3, 5, 7, etc. The determination of prime numbers is a common algorithm problem. This article will introduce how to use Python to write a simple and efficient prime number determination algorithm.

First of all, we need to clarify the conditions for judging prime numbers. For a positive integer n, if there is a number k that satisfies 2

Next, we can write code to implement the prime number judgment algorithm. The following is a sample code written in Python:

import math

def is_prime(n):
    # 排除小于2的数
    if n < 2:
        return False
    
    # 循环判断2到sqrt(n)之间的数是否能整除n
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    
    # 如果没有找到能整除n的数，则n是素数
    return True

# 测试示例
print(is_prime(2))    # 输出：True
print(is_prime(3))    # 输出：True
print(is_prime(4))    # 输出：False
print(is_prime(17))   # 输出：True
print(is_prime(18))   # 输出：False

In the above code, we first introduce the math module to use the sqrt function to calculate the square root of n. Then, we define an is_prime function that accepts a positive integer n as a parameter.

Inside the is_prime function, we first exclude numbers less than 2, because according to the definition of prime numbers, prime numbers must be greater than or equal to 2. Then, we use a loop to determine whether n can be divided in the range from 2 to sqrt(n). If a number is found that divides n, that is, n is not a prime number, we immediately return False. If no number is found that can divide n evenly after the loop ends, then n is a prime number and we return True.

Finally, we can test the example by calling the is_prime function. Entering different parameters, we can see the correct prime number judgment results.

Of course, the above code is just a simple algorithm to implement prime number judgment. For the prime number judgment of large numbers, there are more efficient algorithms, such as Erathosthenes Sieve. Readers can further learn and explore these algorithms to achieve more efficient prime number judgment.

The above is the detailed content of How to use Python to implement the prime number judgment algorithm?. For more information, please follow other related articles on the PHP Chinese website!