acokikoy's notes

ぐずなじぶんに焦らない。ひとつずつ丁寧に定着させる。

毎朝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

今回は特になし

その他

素因数 - Wikipedia

素因数分解という用語を遙か昔に忘れていまちた。お恥ずい ^^;;

数学において、ある自然数の素因数(そいんすう、英: prime factor)とは、その約数になる素数のことである。
ある数の素因数を求めてその積の形で表すことを素因数分解という。
例えば 60 は 22×3×5 と素因数分解されるので 60 の相異なる素因数は 2, 3, 5 の3つである。
また、7 は素数であるため、7 の素因数は 7 自身のみとなる。

2つの自然数が互いに素であることと、2つの自然数が共通の素因数を持たないことは同値である。
なお 1 は素因数を持たない数であり、したがって 1 は全ての(1 自身を含めた)自然数と互いに素である。

自然数素因数分解の結果は、素因数を掛ける順番の違いを除けば一意的に決まる。 この事実は算術の基本定理と呼ばれている。