#17/20 Time Complexity: Primalityh [Cracking the Coding Interview Challenges]

#17 Time Complexity: Primality

www.hackerrank.com

素数判定を行う問題。 以下のような入力が与えられる。

3
12
5
7

一行目はデータの数。それ以降の数に対して、素数かどうか判定を行い、素数であれば'Prime'、そうでなければ'Not prime'を出力する。 上記の場合の出力は以下となる。

Not prime
Prime
Prime

solution

単純な試し割りではタイムアウトでテストケースをパスできない。

試し割りよりも高速なエラトステネスの篩アルゴリズムで解く。 以下はrubyでの解。

def isPrime(num)
    return true if num == 2
    return false if num <= 1 || num % 2 == 0
    ary = (3..Math.sqrt(num).floor).to_a

    while val = ary.shift
        return false if num % val == 0
        ary.delete_if{ |v| v % val == 0 }
    end
    return true
end

input = $stdin.read.split("\n").map(&:to_i)
n = input.shift
n.times { puts isPrime(input.shift) ? 'Prime' : 'Not prime' }

github.com

素数判定について

素数判定 - Wikipedia

エラトステネスの篩とは

エラトステネスの篩 - Wikipedia

計算量(ランダウ記号)について

ランダウの記号 - Wikipedia

計算量算出については、この記事が非常に優しかった。 [初心者向け] プログラムの計算量を求める方法 by @cotrpepe on @Qiita http://qiita.com/cotrpepe/items/1f4c38cc9d3e3a5f5e9c