迹忆客 专注技术分享

当前位置:主页 > 学无止境 > 编程语言 > Python >

在 Python 中查找素因数

作者:迹忆客 最近更新:2023/06/27 浏览次数:

本篇文章将介绍如何在 Python 中执行素因数分解。


质因数分解概述

在数学中,数字的因子是那些可以除以给定数字且余数为零的数字。

素数是唯一的数字,只有两个因子,一和数字本身。 此类数字的一些示例包括 3、7、11、13 等。

质因数分解是指找出所有相乘构成原始数字的质数。 我们可以考虑数字 6 的一个简单例子。

该数的质因数分解产生两个因数:2 和 3。


在 Python 中查找质因数的不同方法

我们可以通过多种方式找到指定数字的质因数。 本文将演示下面列出的三种方法:

  • 创建自定义函数
  • 使用埃拉托斯特尼筛法
  • 使用 primefac 模块

让我们从在 Python 中创建自定义函数开始。

执行质因数分解的自定义函数

在数学中,最基本的质因数分解方法是重复除法。 我们反复将数字除以素数。 我们可以在 Python 中使用嵌套循环来实现这一点。

第一个循环确定一个数字是否是素数。 第二个循环将该素数与给定数相除。

如果余数为零,我们将质数附加到列表中。 该函数返回最终列表。 请参阅下面的代码。

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 的质因数分解。 // 除法运算符确保返回的余数是整数。

使用埃拉托斯特尼筛法进行素因数分解

埃拉托斯特尼筛法算法返回低于给定数字的所有素数。

它标记小于给定数字的值,并且可除以素数的平方以返回所有小于给定数字的素数。

我们可以用它在 Python 中执行素因数分解。 首先,我们找到所需数字以下的质数,然后将它们除以给定的数字以查看其质因数分解。

请参阅以下代码围栏示例:

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]

在上面的代码示例中,我们首先创建一个实现埃拉托色尼筛法的函数,以查找 20 以下的素数。

然后我们创建另一个函数,使用这个素数列表来返回其素数分解。


使用 primefac 模块执行素因子分解

primefac 模块用于执行有关素数的计算。 它可以有效地处理大量计算。

我们可以使用该模块的 primefac() 函数进行素数分解。 它返回可以使用列表构造函数转换为列表的生成器对象。

请参阅下面的代码:

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

输出:

[2, 2, 5]

转载请发邮件至 1244347461@qq.com 进行申请,经作者同意之后,转载请以链接形式注明出处

本文地址:

相关文章

Pandas read_csv()函数

发布时间:2024/04/24 浏览次数:254 分类:Python

Pandas read_csv()函数将指定的逗号分隔值(csv)文件读取到 DataFrame 中。

Pandas 追加数据到 CSV 中

发布时间:2024/04/24 浏览次数:352 分类:Python

本教程演示了如何在追加模式下使用 to_csv()向现有的 CSV 文件添加数据。

Pandas 多列合并

发布时间:2024/04/24 浏览次数:628 分类:Python

本教程介绍了如何在 Pandas 中使用 DataFrame.merge()方法合并两个 DataFrames。

Pandas loc vs iloc

发布时间:2024/04/24 浏览次数:837 分类:Python

本教程介绍了如何使用 Python 中的 loc 和 iloc 从 Pandas DataFrame 中过滤数据。

扫一扫阅读全部技术教程

社交账号
  • https://www.github.com/onmpw
  • qq:1244347461

最新推荐

教程更新

热门标签

扫码一下
查看教程更方便