제곱수 판별 알고리즘

정수 N이 주어졌을 때, N=k*k로 나타내어지는 정수 k가 존재하는지 판별하는 알고리즘이다.

sqrt 함수의 시간복잡도가 O(logN)이라고 가정하면, 알고리즘의 시간복잡도는 O(logN)이 된다.

 

int issqrt(int n){
    int sq=(int)(sqrt(n)+0.5);
    if(sq*sq==n) return sq;
    else return -1;
}