Skip to content

Instantly share code, notes, and snippets.

@viveksyngh
Created August 3, 2015 12:28
Show Gist options
  • Save viveksyngh/cbd050d2eb1ec3faf4ca to your computer and use it in GitHub Desktop.
Save viveksyngh/cbd050d2eb1ec3faf4ca to your computer and use it in GitHub Desktop.
Given a positive integer which fits in a 32 bit signed integer, find if it can be expressed as A^P where P > 1 and A > 0. A and P both should be integers.
#Given a positive integer which fits in a 32 bit signed integer,
#Find if it can be expressed as A^P where P > 1 and A > 0. A and P both should be integers.
def isPower(A):
"""
Returns True if number can be expressed as A^P where P > 1 and A > 0
:param: A an integer
:return: True if it can be expressed as A^P otherwise False
"""
if A == 1 :
return True
elif A <= 3:
return False
for i in range(2, 33) :
temp = self.newtonRaphson(i, A)
if temp == int(temp) :
return True
return False
def newtonRaphson(k, n):
"""
Newton Raphson method for finding kth root of an integer n
:param: k an integer, n is also an integer
:return: kth root of n
"""
n = float(n)
u, s = n, n+1
while u < s:
s = u
t = (k-1) * s + n / pow(s, k-1)
u = t / k
return s
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment