#17 Time Complexity: Primality
素数判定を行う問題。 以下のような入力が与えられる。
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' }
素数判定について
エラトステネスの篩とは
計算量(ランダウ記号)について
計算量算出については、この記事が非常に優しかった。 [初心者向け] プログラムの計算量を求める方法 by @cotrpepe on @Qiita http://qiita.com/cotrpepe/items/1f4c38cc9d3e3a5f5e9c