けいさんしつりょう
質問:
1つの数の素因数の個数を計算し、1は素因数ではない.例えば20=2*2*5、2、2、5は20の3つの素因数です.
考え方:
小さい時から大きい時まで、Nの因数Mを探し当てて、再帰的にMとN/Mの素因数を探します.
1つの数の素因数の個数を計算し、1は素因数ではない.例えば20=2*2*5、2、2、5は20の3つの素因数です.
考え方:
小さい時から大きい時まで、Nの因数Mを探し当てて、再帰的にMとN/Mの素因数を探します.
def count_prime(number, expr):
count = 0
for i in range(2, number/2 + 1):
if number%i == 0:
(count_i, epxr) = count_prime(i, expr)
if count_i == 0:
expr += "%s * "%i
count += 1
else:
count += count_i
left = number/i
(count_left, expr) = count_prime(left, expr)
if count_left == 0:
expr += "%s * "%left
count += 1
else:
count += count_left
break
return (count, expr)
number = input("input a number: ")
(count, expr) = count_prime(number, "")
print("There are %d primes for %d"%(count, number))
print("expr is %s"%expr[:-3])