快捷導(dǎo)航

Python計(jì)算質(zhì)數(shù)的方法總結(jié)

更新時(shí)間：2023年11月03日 08:27:32 作者：濤哥聊Python

質(zhì)數(shù)（Prime?Number）是指大于1且只能被1和自身整除的正整數(shù),計(jì)算質(zhì)數(shù)是數(shù)論中的一個(gè)經(jīng)典問(wèn)題,本文將介紹python中多種計(jì)算質(zhì)數(shù)的方法,希望對(duì)大家有所幫助

一、基礎(chǔ)方法

1.1 暴力法

最簡(jiǎn)單的方法是使用暴力法，逐個(gè)檢查每個(gè)正整數(shù)是否為質(zhì)數(shù)。這種方法對(duì)于小數(shù)字是有效的，但在大數(shù)字上效率很低。

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

1.2 優(yōu)化暴力法

可以通過(guò)減少檢查的范圍來(lái)優(yōu)化暴力法。因?yàn)橘|(zhì)數(shù)必定大于1，所以只需檢查2到√n之間的數(shù)是否能整除n。

import math

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

二、更高效的方法

2.1 埃拉托斯特尼篩法（Sieve of Eratosthenes）

埃拉托斯特尼篩法是一種高效的方法，用于生成一定范圍內(nèi)的所有質(zhì)數(shù)。它通過(guò)不斷排除合數(shù)來(lái)找到質(zhì)數(shù)。

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p**2 <= n:
        if is_prime[p]:
            for i in range(p**2, n + 1, p):
                is_prime[i] = False
        p += 1
    primes = [i for i in range(2, n + 1) if is_prime[i]]
    return primes

2.2 Miller-Rabin素?cái)?shù)測(cè)試

Miller-Rabin素?cái)?shù)測(cè)試是一種概率性的方法，用于測(cè)試一個(gè)數(shù)是否為質(zhì)數(shù)。雖然它不是絕對(duì)確定的，但通?？梢蕴峁┛山邮艿慕Y(jié)果。

import random

def miller_rabin(n, k=5):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False
    
    # 將n-1表示為(2^r) * d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    
    def witness(a, d, n):
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            return True
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                return True
        return False
    
    for _ in range(k):
        a = random.randint(2, n - 2)
        if not witness(a, d, n):
            return False
    return True

三、Python中的質(zhì)數(shù)計(jì)算

Python標(biāo)準(zhǔn)庫(kù)提供了一些用于計(jì)算質(zhì)數(shù)的函數(shù)和模塊，例如sympy和math。

3.1 使用sympy模塊

sympy是Python中用于符號(hào)數(shù)學(xué)的強(qiáng)大庫(kù)，它包含了許多數(shù)論函數(shù)，包括判斷質(zhì)數(shù)的函數(shù)。

from sympy import isprime

print(isprime(17))  # 輸出：True

3.2 使用math模塊

math模塊提供了一些數(shù)學(xué)函數(shù)，包括sqrt函數(shù)，可以用來(lái)優(yōu)化暴力法中的質(zhì)數(shù)判斷。

import math

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

總結(jié)

計(jì)算質(zhì)數(shù)是數(shù)學(xué)和計(jì)算機(jī)科學(xué)中的一個(gè)經(jīng)典問(wèn)題，涉及多種算法和技術(shù)。本文介紹了計(jì)算質(zhì)數(shù)的多種方法，包括基礎(chǔ)方法、更高效的方法和Python中的內(nèi)置函數(shù)和模塊。選擇合適的方法取決于具體的需求和性能要求。

到此這篇關(guān)于Python計(jì)算質(zhì)數(shù)的方法總結(jié)的文章就介紹到這了,更多相關(guān)Python計(jì)算質(zhì)數(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: