Python中查找质因数

翰林君君

如何在Python中进行素因式分解。
质因数分解的概述

在数学中，一个数的因数是指那些可以除以给定数并留下零余数的数字。
质数是只有两个因数的独特数字，一个和数字本身。这类数字的一些例子是3,7,11,13,等等。
素数因数化是指找到所有乘以原数的素数。我们可以考虑一个简单的例子：数字6。
这个数字的质因数分解产生了两个因子，即2和3。
在Python中寻找质因数的不同方法
我们可以用不同的方法找到指定数字的质因数。本文将演示下面列出的三种方法：

• 创建一个自定义函数
  
• 使用Sieve of Eratosthenes
  
• 使用primefac 模块
  

让我们先在Python中创建一个自定义函数。
执行质因数分解的自定义函数

在数学中，最基本的质因数分解方法是重复除法。我们重复地用数字除以质数。我们可以在Python中使用嵌套循环来实现这一点。
第一个循环确定一个数字是否是素数。第二个循环将这个质数和给定的数字相除。
如果余数为零，我们就把这个质数追加到一个列表中。该函数返回最后的列表。请看下面的代码。

1. def p_factorization(n):
2.     i = 2
3.     lst = []
4.     while i * i <= n:
5.         if n % i:
6.             i += 1
7.         else:
8.             n //= i
9.             lst.append(i)
10.     if n > 1:
11.         lst.append(n)
12.     return lst
13. print(p_factorization(20))

复制代码

输出：

1. [2, 2, 5]

复制代码

在上面的例子中，我们返回了20 的质因数。用于除法的// 算子确保返回的余数是一个整数。
Sieve of Eratosthenes 来进行质因式分解

Sieve of Eratosthenes 算法返回低于给定数字的所有质数。
它标记了小于给定数的值，并可被素数的平方除以，以返回小于给定数的所有素数。
我们可以用它在Python中进行素数分解。首先，我们找到低于所需数字的质数，然后用这些质数除以给定的数字，以查看其质因数。
请看下面的代码栅栏作为例子：

1. def sieve_of_erast(number):
2.     maximum = number+1
3.     d = dict() #Python小白学习交流群：711312441
5.     for i in range(2, maximum): d[i] = True
6.     for i in d:
7.         factors = range(i,maximum, i)
8.         for f in factors[1:]:
9.             d[f] = False
10.     lst = [i for i in d if d[i]==True]
11.     return lst
12. def p_factorization(number):
13.     x = number
14.     res = []
15.     lst = sieve_of_erast(number)
16.     i = 0
17.     while(i < len(lst)):
18.         if(x%lst[i]==0):
19.             x = x//lst[i]
20.             res.append(lst[i])
21.             i = 0
22.             if(x == 1):
23.                 break
24.         else:
25.             i = i +1
26.     return res
27. print(p_factorization(20))

复制代码

输出：

1. [2, 2, 5]

复制代码

在上面的代码例子中，我们首先创建一个函数，实现Sieve of Eratosthenes ，找到低于20 的素数。
然后我们创建另一个函数，使用这个素数列表来返回相同的素数因式分解。
primefac 模块来进行素数分解

primefac 模块是用来进行有关质数的计算的。它可以有效地处理大量的计算。
我们可以使用该模块的primefac() 函数进行素数分解。它返回生成器对象，可以使用list 构造函数将其转换为一个列表。
请看下面的代码：

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

复制代码

输出：

1. [2, 2, 5]

复制代码

来源:https://www.cnblogs.com/python1111/p/17673786.html
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！