AMR10C – Square Free Factorization Solution

SPOJ Solution

AMR10C Statement

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

AMR10C Solution

You may also like


Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.