O(√N)で素数判定をする Time Complexity: Primality in Hacker Rank

問題

整数がNが与えられて、Nが素数か否かを判定するメソッドを実装する問題。

www.hackerrank.com

解法

素数とは、1と自身の数のみが約数となる1より大きい数の事。なので、2 ≦ i < Niでループを回し、Nがiで割り切れるかどうかを判定することで素数判定をすることができる。しかし、この解法はO(N)となり間に合わない。

そこで、N = A * B = B * Aという性質に着目すると、iをNまで回す必要が無いことが分る。A * B = B * Aによってiは√Nまで回せば良い。 これによって計算量はO(√N)となる。

ソースコード