Python：每日一题 9

新手·ing

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

新手·ing

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

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

xunzhao

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

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

感觉怪怪的

xunzhao

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

怎么说，缩进太多了？

新手·ing

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

不不
你是大佬
我竟然用了那么多行...

xunzhao

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

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

新手·ing

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

一起努力！

jerryxjr1220

递归写法

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

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

新手·ing

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

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

嗨，大佬
厉害
学习了

冬雪雪冬

在知乎上看到一个程序，写的不错，大家可以借鉴一下。

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))
[2, 3, 3, 5]

新手·ing

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

那都是大佬

lumber2388779

while True:
    try:
        n = (int)(input('请输入一个正整数:'))
        if n <= 0:
            print('输入有误，请重新输入')
            continue
        break
    except ValueError:
        print('输入有误，请重新输入')
primenum = [2,3]
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[j]) == 0:
            n = n//primenum[j]
            print('%d *'%primenum[j],end='')
        else:
            j += 1
            continue
    print('%d '%n,end='')

写了稍微复杂点的

余欲渔

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))

我欲封天

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

用了递归方式，数字到了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) 

技术部-李宁

[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

NwkerWang

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='')
 

抑痒指

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

'''
函数测试
a = [121,0,0]
print(fuction1(a))
print(a)
'''

a = [0,0,0,0]
a[0] = int(input('输入一个数字：'))
print('%d='%a[0],end='')
while fuction1(a):
    print('%d*'%a[1],end = '')
    a[0] = a[2]
print('%d'%a[3])