本篇文章將介紹如何在 Python 中執(zhí)行素因數(shù)分解。

質(zhì)因數(shù)分解概述

在數(shù)學(xué)中，數(shù)字的因子是那些可以除以給定數(shù)字且余數(shù)為零的數(shù)字。

素?cái)?shù)是唯一的數(shù)字，只有兩個(gè)因子，一和數(shù)字本身。 此類數(shù)字的一些示例包括 3、7、11、13 等。

質(zhì)因數(shù)分解是指找出所有相乘構(gòu)成原始數(shù)字的質(zhì)數(shù)。 我們可以考慮數(shù)字 6 的一個(gè)簡(jiǎn)單例子。

該數(shù)的質(zhì)因數(shù)分解產(chǎn)生兩個(gè)因數(shù)：2 和 3。

在 Python 中查找質(zhì)因數(shù)的不同方法

我們可以通過(guò)多種方式找到指定數(shù)字的質(zhì)因數(shù)。 本文將演示下面列出的三種方法：

• 創(chuàng)建自定義函數(shù)
• 使用埃拉托斯特尼篩法
• 使用 primefac 模塊

讓我們從在 Python 中創(chuàng)建自定義函數(shù)開(kāi)始。

執(zhí)行質(zhì)因數(shù)分解的自定義函數(shù)

在數(shù)學(xué)中，最基本的質(zhì)因數(shù)分解方法是重復(fù)除法。 我們反復(fù)將數(shù)字除以素?cái)?shù)。 我們可以在 Python 中使用嵌套循環(huán)來(lái)實(shí)現(xiàn)這一點(diǎn)。

第一個(gè)循環(huán)確定一個(gè)數(shù)字是否是素?cái)?shù)。 第二個(gè)循環(huán)將該素?cái)?shù)與給定數(shù)相除。

如果余數(shù)為零，我們將質(zhì)數(shù)附加到列表中。 該函數(shù)返回最終列表。 請(qǐng)參閱下面的代碼。

def p_factorization(n):
    i = 2
    lst = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            lst.append(i)
    if n > 1:
        lst.append(n)
    return lst

print(p_factorization(20))

輸出:

[2, 2, 5]

在上面的示例中，我們返回了 20 的質(zhì)因數(shù)分解。 // 除法運(yùn)算符確保返回的余數(shù)是整數(shù)。

使用埃拉托斯特尼篩法進(jìn)行素因數(shù)分解

埃拉托斯特尼篩法算法返回低于給定數(shù)字的所有素?cái)?shù)。

它標(biāo)記小于給定數(shù)字的值，并且可除以素?cái)?shù)的平方以返回所有小于給定數(shù)字的素?cái)?shù)。

我們可以用它在 Python 中執(zhí)行素因數(shù)分解。 首先，我們找到所需數(shù)字以下的質(zhì)數(shù)，然后將它們除以給定的數(shù)字以查看其質(zhì)因數(shù)分解。

請(qǐng)參閱以下代碼圍欄示例：

def sieve_of_erast(number):
    maximum = number+1
    d = dict()
    for i in range(2, maximum): d[i] = True

    for i in d:
        factors = range(i,maximum, i)
        for f in factors[1:]:
            d[f] = False
    lst = [i for i in d if d[i]==True]
    return lst

def p_factorization(number):
    x = number
    res = []
    lst = sieve_of_erast(number)
    i = 0
    while(i < len(lst)):
        if(x%lst[i]==0):
            x = x//lst[i]
            res.append(lst[i])
            i = 0
            if(x == 1):
                break
        else:
            i = i +1
    return res


print(p_factorization(20))

輸出:

[2, 2, 5]

在上面的代碼示例中，我們首先創(chuàng)建一個(gè)實(shí)現(xiàn)埃拉托色尼篩法的函數(shù)，以查找 20 以下的素?cái)?shù)。

然后我們創(chuàng)建另一個(gè)函數(shù)，使用這個(gè)素?cái)?shù)列表來(lái)返回其素?cái)?shù)分解。

使用 primefac 模塊執(zhí)行素因子分解

primefac 模塊用于執(zhí)行有關(guān)素?cái)?shù)的計(jì)算。 它可以有效地處理大量計(jì)算。

我們可以使用該模塊的 primefac() 函數(shù)進(jìn)行素?cái)?shù)分解。 它返回可以使用列表構(gòu)造函數(shù)轉(zhuǎn)換為列表的生成器對(duì)象。

請(qǐng)參閱下面的代碼：

import primefac
print(list(primefac.primefac(20)))

輸出:

[2, 2, 5]

到此這篇關(guān)于Python中查找素因數(shù)的方法詳解的文章就介紹到這了,更多相關(guān)Python查找素因數(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論