0

python 質因數問題

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

4 個回答

0
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]]
``````

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

0
ccutmis
iT邦高手 6 級 ‧ 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)]
``````
0

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)))
``````
1
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]
``````