python 質因數問題

python3 質因數問題

yunfei0924 2021-01-11 14:47:30 ‧ 3835 瀏覽

分享至

題目是:寫出一個function 叫 Primefactor(n)，做質因數分解將參數n傳入之後，回傳一個list儲存n的質因數與該質因數出現次數，例如傳入120時120=22235，回傳[(2,3),(3,1),(5,1)]出來
以下是我寫的，但是我就是不知道怎麼做最後一步回傳出質因數的次數
def prime_factoring(n):
divisor = 2
factors = []
while divisor * divisor <= n:
if n % divisor:
divisor += 1
else:
n //= divisor
factors.append(divisor)

if n > 1:
    factors.append(n)

return factors

aNumber = (int)(input("Enter a number:"));
print(prime_factoring(aNumber))

登入發表討論

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

4 個回答

japhenchen

iT邦超人 1 級 ‧ 2021-01-11 15:44:57

import math

def prime_factoring(n):
    factors = list()
    for d in range(2, math.floor(n/2)+1):
        td = prime_factoring(d)
        # 質數 = 除了1跟自己之外，沒有任一數能整除
        if len(list(filter(lambda x : x[1]>0, td)))==0:  
            factors.append([d, 1 if n % d == 0 else 0])
    return factors

aNumber = (int)(input("Enter a number:"))
print(prime_factoring(aNumber))

Enter a number:100
[[2, 1], [3, 0], [5, 1], [7, 0], [11, 0], [13, 0], [17, 0], [19, 0], [23, 0], [29, 0], [31, 0], [37, 0], [41, 0], [43, 0], [47, 0]]

回應 1
分享
檢舉

japhenchen iT邦超人 1 級 ‧ 2021-01-12 08:02:43 檢舉

100: 大於一半，也就50的因數，都不可能整除，所以就排除了50以上的因數

登入發表回應

ccutmis

iT邦高手 2 級 ‧ 2021-01-11 15:51:13

土法煉鋼提供您參考:

def prime_factoring(n):
    divisor = 2
    factors = []
    while divisor * divisor <= n:
        if n % divisor:
            divisor += 1
        else:
            n //= divisor
            factors.append(divisor)
    if n > 1:
        factors.append(n)
    #利用set不重覆的特性取得質數種類
    tmp_set=set(ii for ii in factors)
    final=[]
    for jj in tmp_set:
        #利用list.count()函式取得加總結果
        final.append((jj,factors.count(jj)))
    return final

aNumber = (int)(input("Enter a number:"))
print(prime_factoring(aNumber))

OUTPUT:

Enter a number:120
[(2, 3), (3, 1), (5, 1)]

回應
分享
檢舉

登入發表回應

海綿寶寶

iT邦大神 1 級 ‧ 2021-01-12 09:20:50

from collections import OrderedDict

def prime_factoring(n):
	divisor = 2
	factors = []
	while divisor * divisor <= n:
		if n % divisor:
			divisor += 1
		else:
			n //= divisor
			factors.append(divisor)
	if n > 1:
		factors.append(n)

	return factors

def group_list(lst):       
    res =  [(el, lst.count(el)) for el in lst] 
    return list(OrderedDict(res).items()) 

aNumber = (int)(input("Enter a number:"));
print(group_list(prime_factoring(aNumber)))

回應
分享
檢舉

登入發表回應

froce

iT邦大師 1 級 ‧ 2021-01-13 16:10:31

def prime_factoring(num):
    if num < 2:
        return None
    
    def checkPrime(n):
        for i in range(2, n):
            if n % i == 0:
                return False
        return True
    
    def groupByFactor(n, pri):
        counter = 0
        while n % pri == 0:
            counter += 1
            n = n / pri
        return (pri, counter)
    
    primeFactors = (i for i in range(2, int(num*0.5)+1) if checkPrime(i) and num % i == 0)
    return [groupByFactor(num, i) for i in primeFactors]