论坛 › Python交流 › Python：每日一题 9

新手·ing 发表于 2017-3-28 18:08:35

Python：每日一题 9

题目：将一个正整数分解质因数。例如：输入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   
{:10_298:} 点我上车{:10_298:}   

新手·ing 发表于 2017-3-28 18:09:31

from math import *
#判断n是否为素数
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
#利用递归分解n并打印质因数
def bprime(n):
    if isprime(n):
      print(n)
    else:
      x = 2
      while x <= int(n/2):
            if n%x == 0:
                print(x)
                return bprime(n/x)
            x = x + 1

我的解答！！！

新手·ing 发表于 2017-3-28 18:10:32

@lumber2388779 @ooxx7788 @冬雪雪冬 @jerryxjr1220
新题来了！

xunzhao 发表于 2017-3-28 18:57:49

本帖最后由 xunzhao 于 2017-3-28 19:29 编辑


n=int(input('请输入一个正整数：'))
for i in range(2,n+1):
    if n>=i:
      if n%i ==0:
            while n%i==0:
                n=n/i
                print(i)

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

新手·ing 发表于 2017-3-28 19:25:14

xunzhao 发表于 2017-3-28 18:57
这个可以打印出质因数，不过打印格式好像不太对。。

感觉怪怪的

xunzhao 发表于 2017-3-28 19:30:38

新手·ing 发表于 2017-3-28 19:25
感觉怪怪的

怎么说，缩进太多了？

新手·ing 发表于 2017-3-28 19:39:47

xunzhao 发表于 2017-3-28 19:30
怎么说，缩进太多了？

不不
你是大佬{:10_254:}
我竟然用了那么多行...

xunzhao 发表于 2017-3-28 20:18:32

新手·ing 发表于 2017-3-28 19:39
不不
你是大佬
我竟然用了那么多行...

我是新手才来的，希望逐步进步

新手·ing 发表于 2017-3-28 21:02:54

xunzhao 发表于 2017-3-28 20:18
我是新手才来的，希望逐步进步

一起努力！

jerryxjr1220 发表于 2017-3-28 21:23:16

本帖最后由 jerryxjr1220 于 2017-3-28 21:41 编辑

递归写法
def zys(n, lst=[]):
    primes = * int(n**0.5 + 1)
    primes, primes = False, False
    for i, prime in enumerate(primes):
      if prime:
            for j in range(i * i, int(n**0.5 + 1), i):
                primes = False
    primelist =
    for p in primelist:
      if n % p == 0:
            return zys(n / p, lst + )
    return lst +

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

新手·ing 发表于 2017-3-28 21:28:33

jerryxjr1220 发表于 2017-3-28 21:23
递归写法

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

嗨，大佬
厉害
学习了

冬雪雪冬 发表于 2017-3-28 22:54:27

在知乎上看到一个程序，写的不错，大家可以借鉴一下。
def primefactors(n):
    '''Generate all prime factors of n.'''
    f = 2
    while f * f <= n:
      while not n % f:
            yield f
            n //= f
      f += 1
    if n > 1:
      yield n

>>> list(primefactors(90))

新手·ing 发表于 2017-3-29 16:54:18

冬雪雪冬 发表于 2017-3-28 22:54
在知乎上看到一个程序，写的不错，大家可以借鉴一下。

那都是大佬{:10_243:}

lumber2388779 发表于 2017-3-30 11:22:43

while True:
    try:
      n = (int)(input('请输入一个正整数:'))
      if n <= 0:
            print('输入有误，请重新输入')
            continue
      break
    except ValueError:
      print('输入有误，请重新输入')
primenum =
if n == 1:
    print('1的质因数为1')
elif n < 4:
    print('%d的质因数为%d' %(n,n))
else:
    for i in range(4,n+1):
      maxnum = int(i**0.5)
      minnum = 2
      flag = True
      while True:
            if i%maxnum == 0:
                flag = False
                break
            elif i%minnum == 0:
                flag = False
                break
            elif minnum == maxnum or (minnum+1) == maxnum:
                flag = True
                break
            else:
                maxnum -= 1
                minnum += 1
      if flag:
            primenum.append(i)
j = 0
if n in primenum:
    print('%d的质因数为 %d' %(n,n))
else:
    print('%d =' %n,end='')
    while n not in primenum:
      if (n%primenum) == 0:
            n = n//primenum
            print('%d *'%primenum,end='')
      else:
            j += 1
            continue
    print('%d '%n,end='')

写了稍微复杂点的

余欲渔 发表于 2017-4-11 14:58:09

def zs(x):
    global zys
    xs=int(x**0.5)
    for i in range(2,xs+1):
      if x%i==0:
            zys.append(int(i))
            return zs(x/i)
    zys.append(int(x))
    return zys         

zys=[]
print(zs(90))

我欲封天 发表于 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)

solomonxian 发表于 2017-4-26 20:40:54

用了递归方式，数字到了19位数后就有明显卡滞了

def de_factor(n):
    """将整数n分解质因数后打印出来"""
   
    if n< 0:# 负数把符号抽出来
      print('-',end='')
      return de_factor(-n)
    elif n <= 3:
      print(n)# 0,1,2,3 直接打印
    else:
      sqrt_n = int(n**0.5)+2
      for i in range(2, sqrt_n):
            if n%i == 0:
                print("%d *"% i,end='')
                return de_factor(n//i)   
            else:
                pass
      print(n)

技术部-李宁 发表于 2017-5-2 16:53:27

# cat nine.py
#coding: utf-8

def parse(num, chushu = 2, res = ''):
    if num < 1:
      print('Too small')
      return
    if0 < 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)
# python2 nine.py
2*3*3*5

NwkerWang 发表于 2017-5-30 22:23:30

n = int(input("please input the number:"))
if n == 1:
    print (n,'=',n)
else:
    print (n,'=',end=' ')
if n > 1:
    while n > 1:
      i = 2
      while i<=n:
            if n%i==0:
                print (i,end='')
                n /= i
                break
            i += 1
      if n>1:
            print ('*',end='')

抑痒指 发表于 2017-6-10 15:50:59

import math
def fuction1(a):
    '''找到a的最小质数，通时返回最大质数,有则返回1，无返回0'''
    a = 2
    a = int(math.sqrt(a))
    i = a
    for a in range(2,i+1):
      for a in range(i,a):
            if a * a == a:
                a = a
                return 1
    return 0

'''
函数测试
a =
print(fuction1(a))
print(a)
'''

a =
a = int(input('输入一个数字：'))
print('%d='%a,end='')
while fuction1(a):
    print('%d*'%a,end = '')
    a = a
print('%d'%a)
   

查看完整版本: Python：每日一题 9