問題
整数がNが与えられて、Nが素数か否かを判定するメソッドを実装する問題。
www.hackerrank.com
解法
素数とは、１と自身の数のみが約数となる１より大きい数の事。なので、２ ≦ i < Nのiでループを回し、Nがiで割り切れるかどうかを判定することで素数判定をすることができる。しかし、この解法はO(N)となり間に合わない。
そこで、N = A * B = B * Aという性質に着目すると、iをNまで回す必要が無いことが分る。A * B = B * Aによってiは√Nまで回せば良い。
これによって計算量はO(√N)となる。
