AMR10C - Square Free Factorization
You all know about factorization of an integer. Here we want you to factor a number into as few factors as possible. That is easy, you say, just have the number itself, and that will be the smallest number of factors i.e. 1.
But wait, I haven't finished -- each of the factors that you find must be square-free. A square-free number, however you factor it, won't have any factor that is a perfect square. Of course, you can never include 1 as a factor.
The first line of input is the number of test cases T.
The next T lines each have an integer N.
For each testcase, output the smallest number of square-free factors.
T <= 104
2 <= N <= 106
SAMPLE INPUT 2 6 8 SAMPLE OUTPUT 1 3
Nice Que :) AC 0.00s in first Go :D
very nice problem :) very creative :D
Question can be restated as :
Last edit: 2015-11-07 20:31:21
Sieve+fast I/O...AC in 1.19 sec
Anubhav Balodhi :
Mathematical one ^_^
nice !!! :)
what will be the answer for 44?