鱼C论坛

 找回密码
 立即注册
查看: 10427|回复: 84

[技术交流] Python:每日一题 9

[复制链接]
发表于 2017-3-28 18:08:35 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。
程序分析对n进行分解质因数,应先找到一个最小的质数k,然后按下述步骤完成:
(1)如果这个质数恰等于n,则说明分解质因数的过程已经结束,打印出即可。
(2)如果n<>k,但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数你n,重复执行第一步。
(3)如果n不能被k整除,则用k+1作为k的值,重复执行第一步。


欢迎小伙伴们,一起答题!
如果你有能力,欢迎加入我们!
已经上车老司机:@ooxx7788 @lumber2388779   
点我上车  

评分

参与人数 1鱼币 +5 收起 理由
山岂乎不在高 + 5 无条件支持楼主!

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2017-3-28 18:09:31 | 显示全部楼层
  1. from math import *
  2. #判断n是否为素数
  3. def isprime(n):
  4.     if n <= 1:
  5.         return 0
  6.     m = int(sqrt(n))+1
  7.     for x in range(2,m):
  8.         if n%x == 0:
  9.             return 0
  10.     return 1
  11. #利用递归分解n并打印质因数
  12. def bprime(n):
  13.     if isprime(n):
  14.         print(n)
  15.     else:
  16.         x = 2
  17.         while x <= int(n/2):
  18.             if n%x == 0:
  19.                 print(x)
  20.                 return bprime(n/x)
  21.             x = x + 1
复制代码

我的解答!!!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-3-28 18:10:32 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2017-3-28 18:57:49 | 显示全部楼层
本帖最后由 xunzhao 于 2017-3-28 19:29 编辑

  1. n=int(input('请输入一个正整数:'))
  2. for i in range(2,n+1):
  3.     if n>=i:
  4.         if n%i ==0:
  5.             while n%i==0:
  6.                 n=n/i
  7.                 print(i)
复制代码


这个可以打印出质因数,不过打印格式好像不太对。。

评分

参与人数 2荣誉 +1 鱼币 +1 贡献 +1 收起 理由
KentChen + 1
新手·ing + 1 + 1 支持楼主!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 3 反对 0

使用道具 举报

 楼主| 发表于 2017-3-28 19:25:14 | 显示全部楼层
xunzhao 发表于 2017-3-28 18:57
这个可以打印出质因数,不过打印格式好像不太对。。

感觉怪怪的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-28 19:30:38 | 显示全部楼层

怎么说,缩进太多了?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-3-28 19:39:47 | 显示全部楼层
xunzhao 发表于 2017-3-28 19:30
怎么说,缩进太多了?

不不
你是大佬
我竟然用了那么多行...
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-28 20:18:32 | 显示全部楼层
新手·ing 发表于 2017-3-28 19:39
不不
你是大佬
我竟然用了那么多行...

我是新手才来的,希望逐步进步
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-3-28 21:02:54 | 显示全部楼层
xunzhao 发表于 2017-3-28 20:18
我是新手才来的,希望逐步进步

一起努力!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-28 21:23:16 | 显示全部楼层
本帖最后由 jerryxjr1220 于 2017-3-28 21:41 编辑

递归写法
  1. def zys(n, lst=[]):
  2.     primes = [True] * int(n**0.5 + 1)
  3.     primes[0], primes[1] = False, False
  4.     for i, prime in enumerate(primes):
  5.         if prime:
  6.             for j in range(i * i, int(n**0.5 + 1), i):
  7.                 primes[j] = False
  8.     primelist = [i for i, prime in enumerate(primes) if prime]
  9.     for p in primelist:
  10.         if n % p == 0:
  11.             return zys(n / p, lst + [p])
  12.     return lst + [n]
复制代码

程序本身没什么要讲的,唯一要说明的是,注意大数运算,效率怎么样?


评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
新手·ing + 1 + 1 支持楼主!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

 楼主| 发表于 2017-3-28 21:28:33 | 显示全部楼层
jerryxjr1220 发表于 2017-3-28 21:23
递归写法

程序本身没什么要讲的,唯一要说明的是,注意大数运算,比如当n=100000000时,效率还怎么样?
...

嗨,大佬
厉害
学习了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-28 22:54:27 | 显示全部楼层
在知乎上看到一个程序,写的不错,大家可以借鉴一下。
  1. def primefactors(n):
  2.     '''Generate all prime factors of n.'''
  3.     f = 2
  4.     while f * f <= n:
  5.         while not n % f:
  6.             yield f
  7.             n //= f
  8.         f += 1
  9.     if n > 1:
  10.         yield n
复制代码

  1. >>> list(primefactors(90))
  2. [2, 3, 3, 5]
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 2 反对 0

使用道具 举报

 楼主| 发表于 2017-3-29 16:54:18 | 显示全部楼层
冬雪雪冬 发表于 2017-3-28 22:54
在知乎上看到一个程序,写的不错,大家可以借鉴一下。

那都是大佬
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-30 11:22:43 | 显示全部楼层
  1. while True:
  2.     try:
  3.         n = (int)(input('请输入一个正整数:'))
  4.         if n <= 0:
  5.             print('输入有误,请重新输入')
  6.             continue
  7.         break
  8.     except ValueError:
  9.         print('输入有误,请重新输入')
  10. primenum = [2,3]
  11. if n == 1:
  12.     print('1的质因数为1')
  13. elif n < 4:
  14.     print('%d的质因数为%d' %(n,n))
  15. else:
  16.     for i in range(4,n+1):
  17.         maxnum = int(i**0.5)
  18.         minnum = 2
  19.         flag = True
  20.         while True:
  21.             if i%maxnum == 0:
  22.                 flag = False
  23.                 break
  24.             elif i%minnum == 0:
  25.                 flag = False
  26.                 break
  27.             elif minnum == maxnum or (minnum+1) == maxnum:
  28.                 flag = True
  29.                 break
  30.             else:
  31.                 maxnum -= 1
  32.                 minnum += 1
  33.         if flag:
  34.             primenum.append(i)
  35. j = 0
  36. if n in primenum:
  37.     print('%d的质因数为 %d' %(n,n))
  38. else:
  39.     print('%d =' %n,end='')
  40.     while n not in primenum:
  41.         if (n%primenum[j]) == 0:
  42.             n = n//primenum[j]
  43.             print('%d *'%primenum[j],end='')
  44.         else:
  45.             j += 1
  46.             continue
  47.     print('%d '%n,end='')
复制代码

写了稍微复杂点的

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
新手·ing + 1 + 1 支持楼主!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 2 反对 0

使用道具 举报

发表于 2017-4-11 14:58:09 | 显示全部楼层
  1. def zs(x):
  2.     global zys
  3.     xs=int(x**0.5)
  4.     for i in range(2,xs+1):
  5.         if x%i==0:
  6.             zys.append(int(i))
  7.             return zs(x/i)
  8.     zys.append(int(x))
  9.     return zys         

  10. zys=[]
  11. print(zs(90))
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
新手·ing + 3 + 3 支持楼主!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-16 20:55:26 | 显示全部楼层
from math import *
def isprime(n):#判断是否为素数
    if n <= 1:
        return 0
    m = int(sqrt(n)) + 1
    for x in range(2, m):
        if n%x == 0:
            return 0
    return 1

def bprime(n):
    if isprime(n):
        print(n)
    else:
        x = 2
        while x <= int(n/2):
            if n%x == 0:
                print("%.1f *" % x, end='')
                return bprime(n/x)
            x = x + 1
print("30 = ", end='')
bprime(30)

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
新手·ing + 3 + 3 支持楼主!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-26 20:40:54 | 显示全部楼层
用了递归方式,数字到了19位数后就有明显卡滞了

  1. def de_factor(n):
  2.     """将整数n分解质因数后打印出来"""
  3.    
  4.     if n< 0:  # 负数把符号抽出来
  5.         print('-',end='')
  6.         return de_factor(-n)
  7.     elif n <= 3:
  8.         print(n)  # 0,1,2,3 直接打印
  9.     else:
  10.         sqrt_n = int(n**0.5)+2
  11.         for i in range(2, sqrt_n):
  12.             if n%i == 0:
  13.                 print("%d *"% i,end='')
  14.                 return de_factor(n//i)   
  15.             else:
  16.                 pass
  17.         print(n)
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
新手·ing + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-5-2 16:53:27 | 显示全部楼层
[root@1pycentos7 everyday]# cat nine.py
#coding: utf-8

def parse(num, chushu = 2, res = ''):
    if num < 1:
        print('Too small')
        return
    if  0 < num < 3:
        return num
    if num % chushu == 0 and num / chushu != 1:
        
        return parse(num / chushu, 2, res + str(chushu))
    elif num % chushu != 0:
        return parse(num , chushu +1, res)
    elif num == chushu:
        if len(res) == 0:
            return chushu
        return '*'.join(res+str(chushu))
a = parse(90)
print(a)
[root@1pycentos7 everyday]# python2 nine.py
2*3*3*5
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-5-30 22:23:30 | 显示全部楼层
  1. n = int(input("please input the number:"))
  2. if n == 1:
  3.     print (n,'=',n)
  4. else:
  5.     print (n,'=',end=' ')
  6. if n > 1:
  7.     while n > 1:
  8.         i = 2
  9.         while i<=n:
  10.             if n%i==0:
  11.                 print (i,end='')
  12.                 n /= i
  13.                 break
  14.             i += 1
  15.         if n>1:
  16.             print ('*',end='')
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-6-10 15:50:59 | 显示全部楼层
  1. import math
  2. def fuction1(a):
  3.     '''找到a的最小质数,通时返回最大质数,有则返回1,无返回0'''
  4.     a[1] = 2
  5.     a[2] = int(math.sqrt(a[0]))
  6.     i = a[2]
  7.     for a[1] in range(2,i+1):
  8.         for a[2] in range(i,a[0]):
  9.             if a[1] * a[2] == a[0]:
  10.                 a[3] = a[2]
  11.                 return 1
  12.     return 0

  13. '''
  14. 函数测试
  15. a = [121,0,0]
  16. print(fuction1(a))
  17. print(a)
  18. '''

  19. a = [0,0,0,0]
  20. a[0] = int(input('输入一个数字:'))
  21. print('%d='%a[0],end='')
  22. while fuction1(a):
  23.     print('%d*'%a[1],end = '')
  24.     a[0] = a[2]
  25. print('%d'%a[3])
  26.    
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 01:57

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表