## Prime Power Predicate

### March 13, 2015

In today’s exercise we write a function that determines if a number *n* can be written as *p ^{k}* with

*p*prime and

*k*> 0 an integer. We looked at this function in a previous exercise where we tested each prime exponent up to the base-2 logarithm of

*n*.

Henri Cohen describes a better way to make that determination in Algorithm 1.7.5 of his book *A Course in Computational Algebraic Number Theory*. He exploits Fermat’s Little Theorem and the witness to the compositeness of *n* that is found by the Miller-Rabin primality tester. Cohen proves that if *a* is a witness to the compositeness of *n*, in the sense of the Miller-Rabin test, then gcd(*a ^{n}* −

*a*,

*n*) is a non-trivial divisor of

*n*(that is, it is between 1 and

*n*).

Your task is to write a program that determines if a number can be written as a prime power and, if so, returns both the prime and the exponent. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Port of the given python code to Java:

However this solution has two drawbacks:

1) The input is of type “long”, so it cannot compute for big numbers like 1940255363782247**37

2) It does *not* compute logarithm by binary search but by repeated division only.

I am working on the proper solution with these drawbacks addressed. I will post it if and when i crack it :)

randLong method is copied shamelessly from http://stackoverflow.com/a/2546186