演習課題「素因数分解を実装する」
整数nが入力として与えられるので、nを素因数分解したときに現れる素数を小さい方から順に改行区切りで出力してください。同じ素数が複数回現れる場合は、現れる回数だけその素数を出力してください。
右側のコードエリアには、入力nを受け取り、関数factorizeによって素因数分解をおこない、その結果として現れる素数を小さい方から順に改行区切りで出力するコードが用意されています。関数factorizeのコードを書き加え、コードを完成させてください。
期待する出力値
2
2
2
演習課題「約数の個数を求める」
整数nが入力として与えられるので、nの約数が何個あるかを求めてください。
右側のコードエリアには、入力nを受け取り、関数calcNumOfPrimeFactorsによってnの約数の個数を求め、出力するコードが用意されています。関数calcNumOfPrimeFactorsのコードを書き加え、コードを完成させてください。
期待する出力値
9
＃05:素因数分解・約数の個数
このチャプターでは、素因数分解と、約数の個数の求め方について学習します。
# 整数を受け取り、素因数分解をおこなって[素因数、個数]の連想配列(辞書)を返す関数
def factorize(n):
primes = {}
for i in range(2, int(n**0.5)+1):
if n % i > 0:
continue
exp = 0
while n % i == 0:
exp += 1
n //= i
primes[i] = exp
if n != 1:
primes[n] = 1
return primes
n = int(input())
table = factorize(n)
for prime in table:
exp = table[prime]
for _ in range(exp):
print(prime)
# 整数を受け取り、素因数分解をおこなって[素因数、個数]の連想配列(辞書)を返す関数
def factorize(n):
primes = {}
for i in range(2, int(n**0.5)+1):
if n % i > 0:
continue
exp = 0
while n % i == 0:
exp += 1
n //= i
primes[i] = exp
if n != 1:
primes[n] = 1
return primes
# 整数を受け取り、約数の個数を返す関数
def calcNumOfPrimeFactors(n):
primes = factorize(n)
numOfFactors = 1
for num in primes.values():
numOfFactors *= (num + 1)
return numOfFactors
n = int(input())
numOfPrimeFactors = calcNumOfPrimeFactors(n)
print(f"{n} の約数は {numOfPrimeFactors} 個")
他言語では「連想配列」というデータ構造が使われていますが、Pythonでは同様のデータ構造である「辞書」と呼ばれるデータ構造を使います。