Question

A positive integer N is a power if it is of the form q^k, where q, k are positive integers and k > 1. Give an efficient algorithm that takes as input a number N and determines whether it is a square, that is, whether it can be written as q^2 for some positive integer q. What is the running time of your algorithm? write the pseudocode for the algorithm.

Answer 1

   pseudocode ://to find N is a square
isSquare(N):
   i=1
   while(i*i <N)://this loop breaks when i*i = N or i*i is greater than N
       i=i+1
   if(i*i ==N)://means N is a square
       return true
   else:
       return false
//complexity is :O(sqrt(N)) // O(N^(1/2))