TopCoder problem "Powerful" used in SRM 89 (Division I Level One , Division II Level Two)

Problem Statement

A number is a Perfect Square if it can be expressed as k^2 for some positive integer k. A number is a Perfect Power if it can be expressed as k^n (k to the n^th power) for some positive integers k and n, where n and k must both be greater than 1.

Create a class Powerful that contains the method power that takes an int, number, as input and returns the String "<k>^<n>", where <k> to the <n>^th power is equal to number. If a number cannot be represented as a Perfect Power, your method should return "NOT A PERFECT POWER".

Definition

Class:	Powerful
Method:	power
Parameters:	int
Returns:	String
Method signature:	String power(int number)
(be sure your method is public)

Notes

If there is more than one way to express a number as a Perfect Power, your method should express it with the highest exponent possible. (see example 1)

Your method should return "<k>^<n>"; (quotes and angle brackets for clarity only) with no blanks or leading zeroes.

Constraints

number is between 1 and 2,000,000,000 inclusive.

Examples

Returns: "2^3"

Returns: "3^4"

Do NOT return "9^2"

Returns: "NOT A PERFECT POWER"

Returns: "NOT A PERFECT POWER"

2000000000

Returns: "NOT A PERFECT POWER"