yu/logs/*

技術メモ　など

AtCoder ABC149 C 解法メモ（Kotlinで）素数を列挙したい（エラトステネスの篩）

AtCoder Kotlin

エラトステネスの篩と呼ばれる方法で素数を列挙することができるようだったので、参考リンクのものを参照しながらKotlinで書いてみた

解いていた問題

解法メモ

エラトステネスの篩と呼ばれる方法で素数列挙が可能

 /**
  * エラトステネスの篩を利用して素数を列挙したリストを作成
  */
 private fun makePrimes(n: Int): MutableList<Int> {
     val isPrime = MutableList(n + 1) { true }
     isPrime[0] = false
     isPrime[1] = false
 
     for (p in 2..sqrt(n.toDouble()).toInt() + 1) {
         if (isPrime[p]) {
             for (x in p * 2..n step p) {
                 // p^2以上のpの整数倍は全てfalse(=0)にしてふるいにかける
                 isPrime[x] = false
             }
         }
     }
 
     val res = mutableListOf<Int>()
     for (p in 2..n) {
         if (isPrime[p]) {
             res.add(p)
         }
     }
 
     return res
 }

提出した回答

参考