毎朝Codewars@2019.08.07(水): Primes in numbers
毎朝ちびちびCodewars。
[5 kyu] Primes in numbers www.codewars.com
今日のお題：
"""[5 kyu] Primes in numbers https://www.codewars.com/kata/primes-in-numbers 1以上の正の整数 num について、素因数分解した結果を次の書式で返す: "(p1**n1)(p2**n2)...(pk**nk)" - p(i) は昇順に並べること - n(i) が1の場合は、'**1' と書かず省略すること 例: num = 86240 の答えは "(2**5)(5)(7**2)(11)" """
コード
def primeFactors(num): result = '' p = 2 while p <= num: if num % p == 0: n = 0 while num % p == 0: n += 1 num //= p if n == 1: result += f'({p})' else: result += f'({p}**{n})' p += 1 return result
- p=2からはじめて、p が num の約数かチェックする。
- もし 2 で割り切れることがわかったら、2で割り切れるだけ割り続けて、割った回数nをカウントする。
- 割り切れなくなる直前の p と n のペアが 素因数とそのべき乗にあたる
- 割り切れなくなったら pを+1 し、同様のチェックを行う。これを、pがnumを超えるまで繰り返す。
文法、関数・メソッドnote
今回は特になし
その他
素因数分解という用語を遙か昔に忘れていまちた。お恥ずい ^^;;
数学において、ある自然数の素因数（そいんすう、英: prime factor）とは、その約数になる素数のことである。
ある数の素因数を求めてその積の形で表すことを素因数分解という。
例えば 60 は 22×3×5 と素因数分解されるので 60 の相異なる素因数は 2, 3, 5 の3つである。
また、7 は素数であるため、7 の素因数は 7 自身のみとなる。2つの自然数が互いに素であることと、2つの自然数が共通の素因数を持たないことは同値である。
なお 1 は素因数を持たない数であり、したがって 1 は全ての（1 自身を含めた）自然数と互いに素である。
