5
2
A perfect power is a positive integer that's equal to one positive integer, to the power of another positive integer (e.g. ab is a perfect power). Note that trivial solutions (e.g. b=1) are excluded; specifically, the definition requires a ≥ 2 and b ≥ 2.
The task
Write a full program that takes any number of positive integers (separated by newlines) from standard input, and for each such input n, outputs all pairs of positive integers a, b (with a ≥ 2 and b ≥ 2) such that ab = n. Use the syntax a^b
for these pairs. If multiple pairs of outputs are possible for a given input, print all of them, separated by spaces.
Note the victory condition below: the aim here is to optimize the program for speed, not size.
Example test cases
Input
1745041
1760929
1771561
1852321
1868689
1874161
1885129
1907161
1953125
113795717542678488615120001
113795717546049421004105281
Output
1745041 = 1321^2
1760929 = 1327^2
1771561 = 11^6 121^3 1331^2
1852321 = 1361^2
1868689 = 1367^2
1874161 = 37^4 1369^2
1885129 = 1373^2
1907161 = 1381^2
1953125 = 5^9 125^3
113795717542678488615120001 = 10667507560001^2
113795717546049421004105281 = 10667507560159^2
Clarifications
- No more than 10000 inputs will be given on any single run of the program.
- Your program, as written, should be able to handle numbers up to at least 30 digits long (meaning you will likely need to use bignum support). In order for the victory condition to be meaningful, though, the underlying algorithm behind your submission must be capable of working for arbitrary perfect powers, no matter how large they are.
- Each input n will actually be a perfect power, i.e. there will always be at least one output corresponding to each given input.
- There are no restrictions on programming language (as long as the language has sufficient power to complete the task).
Victory condition
The program with the fastest algorithm (i.e. with the fastest complexity) will be the winner. (Note that the fastest known perfect power decomposition algorithms can determine whether a number is a perfect power, and what the base and exponent are, without having to actually factorise the number; you may want to take this into account when choosing the algorithm for your problem.)
In the case that two programs are equally fast by this measure, the tiebreak will be to see which program runs faster in practice (on the stated testcases or, to avoid hard-coding, a similar set of test cases).
3most efficient time complexity and fastest (for finite input) are not equivalent :) – Dr. belisarius – 2011-04-03T13:22:31.187
It's kinda awkward competing for speed in such a fast task, since the program will end up I/O bound. – aaaaaaaaaaaa – 2011-04-03T14:49:53.060
1What if N has no non-trivial power representation? Should we output "N =" or nothing? – Keith Randall – 2011-04-03T15:44:00.520
@Keith Randall:I have updated the constraints. – Quixotic – 2011-04-03T16:06:53.327
downvoted because i/o timing is likely to be a large part of the time cost – l4m2 – 2018-06-05T09:47:07.480