[已解决]求一个数的质数因子,不报错，就是没有结果

猪猪虾

#将一个正整数分解质因数。例如：输入13195，打印13195 = 5*7*13*29
                             # 输入90,打印出90=2*3*3*5
#思路：首先用number对从2开始的质数取余，如果余数为0，表示能被该质数整除，然后再用该数除以该素数，取其除数
#将除数赋值给number,又再次对此数从质数3开始取余，判断是否能被整除，反复重复上述的步骤,直到所存储的因子乘机 == 输入值
#此时的质数为输入的初始number的最大质数因子 
import math
num = int(input("enter the number:"))
factor = []
my_num = 1  #存放所求得质数因子乘积值
number = num

i = 2
while my_num != number:
       #判断i是不是质数
       for j in range(2,int(math.sqrt(i))+1):
           if (i % j) == 0:
               break    #不是质数，结束循环
           elif j == int(math.sqrt(i)):   #判断是否执行到了最后
                #在i是质数的前提下
                if number % i == 0 :
                    shang = number // i     #取商                                                                                  
                    factor.append(i)                                                                                             
                    my_num = my_num * i
                    if  my_num == number:                                                                                              
                          print(factor)
                    else:
                        number = shang  
        
       i = i + 1                          
                     
  

最佳答案

月排行榜 / 总排行榜

java2python

2020-6-23 16:25:48

这个能行，其实看别人程序蛮累的：

num = int(input("enter the number:"))
def prime_f(num):
    f = 2
    factor = []
    while f<int(math.sqrt(num)):
        while num % f == 0:
            factor.append(f)
            num //= f
        f += 1
    factor.append(num)
    return factor
print(prime_f(num))

结果：

enter the number:33552
[2, 2, 2, 2, 3, 3, 233]

跳转到最佳答案楼层

wp231957

你再好好拢一拢，死循环 是一定的了

Twilight6

之前做过一次只是没用开方效率低

def prime_factorization(n):
    prime_list = []
    temp = n
    i = 2
    for i in range(2,n):
        while not(n%i):
            if not (n % i):
                n //= i
                prime_list.append(i)
    if i == 2 or (prime_list == [] and i+1 == temp):
        prime_list.append(temp)
    return prime_list

print(prime_factorization(13195))

java2python

这个能行，其实看别人程序蛮累的：

num = int(input("enter the number:"))
def prime_f(num):
    f = 2
    factor = []
    while f<int(math.sqrt(num)):
        while num % f == 0:
            factor.append(f)
            num //= f
        f += 1
    factor.append(num)
    return factor
print(prime_f(num))

结果：

enter the number:33552
[2, 2, 2, 2, 3, 3, 233]

猪猪虾

java2python 发表于 2020-6-23 16:25
这个能行，其实看别人程序蛮累的：

结果：

难道是我一开始就理解错了题意吗，在进行判断余数是不是为0之前，不需要判断F是不是质数吗

猪猪虾

wp231957 发表于 2020-6-23 16:24
你再好好拢一拢，死循环 是一定的了

求指导，为啥是死循环

java2python

猪猪虾 发表于 2020-6-23 16:44
难道是我一开始就理解错了题意吗，在进行判断余数是不是为0之前，不需要判断F是不是质数吗

理解你想要效率高的想法，不过把质数筛选出来，本身也是很花功夫的，一般不会这么做。
就是对于N:检查2-根号N之间的因数，当发现因数后，Num除以因数，num变小了，他就不需要检查到一开始的根号（num)的地方了，所以这个循环不能用for,需要用while，for循环的首尾是写死的，即便里面num值改变了，也就是根号(num)改变了，他照样执行到原先的根号(num)

猪猪虾

java2python 发表于 2020-6-23 16:51
理解你想要效率高的想法，不过把质数筛选出来，本身也是很花功夫的，一般不会这么做。
就是对于N:检查2- ...

1.你的程序是怎么保证所求得的因数都是质数的，

2.factor.append(num)，为啥可以直接将此时的Num添加到列表里面

java2python

猪猪虾 发表于 2020-6-23 17:00
1.你的程序是怎么保证所求得的因数都是质数的，

2.factor.append(num)，为啥可以直接将此时的Num添加 ...

从2开始一路往上，所有合数，也是有质数相乘得到，而程序里面有

        while num % f == 0:
            factor.append(f)
            num //= f

比如3是质数，也是num的因子，可能有好几个3的因子，但发现3是因子就一直循环，说简单点就是榨干了，里面再也没有3的因子，遇到9就跳过了。
最后除不尽的，留下的就是num，当然可能是1，比如输入16，遇到2，除4次，剩下1，这里可以判断一下，不是1就加入

猪猪虾

java2python 发表于 2020-6-23 17:05
从2开始一路往上，所有合数，也是有质数相乘得到，而程序里面有

比如3是质数，也是num的因子，可能有 ...

原谅我脑子不好，第2个问题我懂了，第一个还是没懂，您换个说法。。

java2python

猪猪虾 发表于 2020-6-23 17:09
原谅我脑子不好，第2个问题我懂了，第一个还是没懂，您换个说法。。

比如52，按道理2是因子，4也是
通过：

while num % f == 0:
            factor.append(f)
            num //= f

num=52,f=2
循环一次
num=26,f=2
循环一次
num=13,f=2
当f=4的时候，这个时候num=13了，因为2的因子已经被除掉了（num都不存在2的因子，哪来的4的因子呢）

猪猪虾

java2python 发表于 2020-6-23 17:12
比如52，按道理2是因子，4也是
通过：

懂了，学到了