python求質(zhì)數(shù)的算法怎么寫

小億
49
2023-12-07 06:07:11

有多種方法可以用Python編寫質(zhì)數(shù)的算法。下面是兩種常見的方法：

方法一：使用除法 該算法通過(guò)逐個(gè)除以小于該數(shù)的所有整數(shù)，判斷是否存在能整除該數(shù)的數(shù)。如果存在則不是質(zhì)數(shù)，否則是質(zhì)數(shù)。

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

# 示例用法
print(is_prime(5))  # 輸出 True
print(is_prime(10)) # 輸出 False

方法二：使用開方 該算法通過(guò)判斷一個(gè)數(shù)是否能被小于等于其平方根的質(zhì)數(shù)整除，判斷是否為質(zhì)數(shù)。這是因?yàn)槿绻粋€(gè)數(shù)可以被大于其平方根的數(shù)整除，那它也一定可以被小于等于其平方根的質(zhì)數(shù)整除。

import math

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

# 示例用法
print(is_prime(5))  # 輸出 True
print(is_prime(10)) # 輸出 False

這兩種算法都可以判斷一個(gè)數(shù)是否為質(zhì)數(shù)，但第二種方法的效率更高，特別是當(dāng)需要判斷大量的數(shù)是否為質(zhì)數(shù)時(shí)，建議使用第二種方法。

0 踩