python 素因子分解
2024-10-12 17:00:54
在使用python解决问题之前,我们先说一下,什么是素因子分解
所谓素因子分解就是,先找这个数的所有约数(约数即:a%b == 0,也就是a可以被b整除)
例如:20的约数集合为 [1, 2, 5, 10, 20]
那么素因子分解呢?
就是从最小的素数约数开始除,也就是这个除数要满足两个条件,一是约数,二是素数
那么这里20的最小的素约数是2,所以我们从2开始除,并且一直除到不能被整出为止:
num = 20
num = num / 2
num = 10(这里num依旧可以被2整除,所以再来一次)
num = num / 2
num = 5 (num很明显除以2不能整除)
所以接下来被除数需要向后走,即5(再取下一个数为除数之前,要先判断是否为素数,这里5为素数,如果不是素数比如4则需要继续向后取)
num = num / 5
num = 1
至此,运算结束。所以,我们得到20的素因子集合为:[2, 2, 5]
那么接下来就是使用python实现的部分了
通过之前的解析过程,我们可以看到我们需要这么两个小模块:
1. 判断数字是否是素数,如果数字本身是素数,那么直接返回1和它本身就可以了,因为素数不能被分解了,即 [1, num]
2. 我们需要获得这个数的所有约数,以便于我们进行作除法
下面是这两个部分的实现:
# 判断是否是素数
def isprime(num):
count = num / 2
while count > 1:
if num % count == 0:
return False
count -= 1
else:
return True
# 得到所有的约数
def getfactors(num):
return [x for x in range(1, num) if num % x == 0]
通过上面两个部分,我们就可以得到所有的基础了,接下来就是运算了
def primefactor(num):
if isprime(num):
return [1,num]
factors = getfactors(num)
retList = []
consult = num
for i in range(1,len(factors)):
if consult == 1:
break
while True:
if consult % factors[i] != 0:
break
if isprime(factors[i]):
consult /= factors[i]
retList.append(factors[i])
else:
break
return retList
ok,最后调用primefactor就可以得到结果了,注意返回的是个list对象哦
最新文章
- linux内核分析作业:以一简单C程序为例,分析汇编代码理解计算机如何工作
- SharePoint Server 2007 简体中文下载
- Ubuntu创建launcher
- Ubuntu16.04.1 安装MyCat
- Hadoop: the definitive guide 第三版 拾遗 第十二章 之Hive初步
- rest服务器
- Android游戏开发实践(1)之NDK与JNI开发04
- Linux中的shell到底是什么
- 描述一下Spring框架的作用和优点?
- 不校验csrf
- Groovy语言学习--语法基础(3)
- Nginx配置实际案例
- Struct(二)
- 小睿开始呼叫用户,然后FS怎么跟用户交互的整个流程原理
- Spring IOC 源码分析
- python中的注释,输入输出和编码及文件
- Hadoop生态圈-桶表和分区表
- js 按字段分组
- Java线程之CompletionService批处理任务
- Delphi XE10下用FireDAC与SQLite连接要注意的问题 转
热门文章
- Java多线程由易到难
- WPF 完美截图 <;二>;
- 主机和VMware中的Linux如实现共享文件夹
- 使用composer更新thinkphp5或则yii2的版本
- Python之作用域
- 洛谷 P3391 【模板】文艺平衡树
- C语言中静态申请内存遇到的错误分析
- Mysql update in报错 [Err] 1093 - You can&#39;t specify target table &#39;company_info&#39; for update in FROM clause
- 去培训机构参加IT培训值不值
- StringUtils工具类常用方法汇总2(截取、去除空白、包含、查询索引)