素因数分解しよう

このレッスンでは、Kotlinで素因数分解を行う方法を学び、繰り返し処理を使った数論アルゴリズムの実装を理解することを目標にします。「Kotlin 素因数分解実装」で調べている方向けです。

素因数分解とは、ある数を素数の掛け算で表すことです。2から順に割り切れるか試し、割り切れたらその数で割り続ける、という手順で求められます。

サンプルコードでは、d = 2から始めて、numがdで割り切れる限りfactors.add(d)で結果に追加しながらnum /= dで割り続け、割り切れなくなったらdを1つ増やすという処理を、numが1になるまで繰り返しています。

初心者がよくつまずくのが、二重ループの構造です。外側のループで割る数dを増やしながら、内側のループで割り切れる限り割り続けるという、2段階の繰り返しの組み合わせが理解のポイントになります。

暗号技術(RSA暗号など)の安全性の根拠にもなっている、数学とコンピュータサイエンスの両方にまたがる重要な考え方です。1という数はどんな数でも割り切れてしまうため、素因数分解の対象からは除外して考える必要があります。

📖 お手本コード

fun primeFactors(n: Int): List<Int> {
    val factors = mutableListOf<Int>()
    var num = n
    var d = 2
    while (num > 1) {
        while (num % d == 0) {
            factors.add(d)
            num /= d
        }
        d++
    }
    return factors
}

fun main() {
    println(primeFactors(60))
    println(primeFactors(97))
}

✍️ あなたのコード

コードを書いたら「実行する」を押してください

🧪 このサイトではKotlinを直接コンパイル・実行できないため、お手本コードと同じ内容を入力できたかをその場で判定します(採点はブラウザ内だけで行われ、どこにも送信されません)。

🎯

ここまでできればゴール達成!
入力された数を素因数分解するツールが作れるようになります。