文档章节

分解质因数

寂寞暴走伤
 寂寞暴走伤
发布于 2016/07/14 19:30
字数 237
阅读 16
收藏 0

问题描述:

将一个正整数分解质因数。例如,输入90,打印出90=2*3*3*5


我的代码:

n=int(raw_input("input a number: "))
a=[]
k=2
while n:
    if n==k:
        a.append(k)
        break
    elif n>=k and n%k==0:
        a.append(k)
        n=n/k
    else:
        k=k+1
print a


我的思路:

对n进行分解质因数,先找到一个最小得质数k,我设为了2:

(1)如果k等于n,则说明过程已经结束,打印出即可;


(2)如果n>=k,且n能被k整除,则打印出k的值,并用n除以k得商,作为新的正整数n,重复执行第一步;


(3)如果n不能被k整除,则用k+1作为k的值,重复执行第一步;


(4)最后打印出所有的质数;


示例代码:

def fun(n):
   res = []
   k = 2
   while k <= n:
       if n % k == 0:
           res.append(k)
           n /= k
       else:
           k += 1
   print res
fun(90)


题目出处:http://www.cheemoedu.com/exercise/54

© 著作权归作者所有

共有 人打赏支持
上一篇: 杨辉三角
下一篇: 角谷猜想
寂寞暴走伤
粉丝 0
博文 40
码字总数 20969
作品 0
南阳
运维
私信 提问
经典算法详解(12)分解质因数

题目:众所周知,任何一个合数(因数不止是1和本身)都可以写成几个质数相乘的形式,这几个质数叫做这个合数的质因数。例如,24=2×2×2×3.把一个合数写成几个质数相乘的形式叫做分解质因数...

ysyouaremyall
2018/07/17
0
0
bzoj4802欧拉函数【Rabin-Miller+pollard_rho】

解题思路: 直接把n用Rabin-Miller+pollardrho算法质因数分解(不会的可以看这里),用欧拉函数的计算式计算即可。 注意pollardrho算法会把n完全质因数分解,所以最后要去重。...

cdsszjj
2018/01/12
0
0
量子计算将能分解任意极大整数,RSA加密或成摆设

就算是一台超级计算机有可能在数年的时间内计算出任意质因数,这也是得不偿失的。为了科学地解决这个问题,麻省理工学院(MIT)的科学家找到了明确的方法。今天,《科学》杂志最新发表的一篇...

雪花又一年
2018/05/15
0
0
BJ模拟 Period on tree【树状数组+哈希】

题目描述: 给定一棵 N 个节点的无根树,每条边上有一个小写英文字母。每次我们选择两个不同的节点 u 和 v,然后依次写下从 u 到 v 的最短路径上每条边上的字母,我们就能得到这条路径对应的...

cdsszjj
2018/04/25
0
0
Python3 初学实践案例(11)判断质数以及计算一个数字的质因数

Python3 初学实践案例(11)判断质数以及计算一个数字的质因数 昨天晚上看到群里有人问如何计算质因数,我想了一下,实现了这个计算质因数的脚本。 质因数(素因数或质因子)在数论里是指能整...

FungLeo
2017/12/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

C++ vector和list的区别

1.vector数据结构 vector和数组类似,拥有一段连续的内存空间,并且起始地址不变。 因此能高效的进行随机存取,时间复杂度为o(1); 但因为内存空间是连续的,所以在进行插入和删除操作时,会造...

shzwork
今天
3
0
Spring之invokeBeanFactoryPostProcessors详解

Spring的refresh的invokeBeanFactoryPostProcessors,就是调用所有注册的、原始的BeanFactoryPostProcessor。 相关源码 public static void invokeBeanFactoryPostProcessors(Configu......

cregu
昨天
4
0
ibmcom/db2express-c_docker官方使用文档

(DEPRECIATED) Please check DB2 Developer-C Edition for the replacement. What is IBM DB2 Express-C ? ``IBM DB2 Express-C``` is the no-charge community edition of DB2 server, a si......

BG2KNT
昨天
3
0
Ubuntu 18.04.2 LTS nvidia-docker2 : 依赖: docker-ce (= 5:18.09.0~3-0~ubuntu-bionic)

平台:Ubuntu 18.04.2 LTS nvidia-docker2 版本:2.0.3 错误描述:在安装nvidia-docker2的时候报dpkg依赖错误 nvidia-docker2 : 依赖: docker-ce (= 5:18.09.0~3-0~ubuntu-bionic) 先看一下依......

Pulsar-V
昨天
4
0
学习笔记1-goland结构体(struct)

写在前面:若有侵权,请发邮件by.su@qq.com告知。 转载者告知:如果本文被转载,但凡涉及到侵权相关事宜,转载者需负责。请知悉! 本文永久更新地址:https://my.oschina.net/bysu/blog/3036...

不最醉不龟归
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部