AMR10C - Square Free Factorization

no tags 

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.

Input

The first line of input is the number of test cases T.
The next T lines each have an integer N.

Output

For each testcase, output the smallest number of square-free factors.

Constraints

T <= 104
2 <= N <= 106

Example

SAMPLE INPUT
2
6
8

SAMPLE OUTPUT
1
3

hide comments
karthik1997: 2016-06-09 17:27:11

Nice Que :) AC 0.00s in first Go :D

Sieve is a complete time consuming and O(sqrt(N) ) factorization is fine

Just write the prime factorization of a number and you can easily figure out the solution.

for example : 12 = (2^2) *3 => ans is 2
Expected Complexity is O( sqrt(N)*log(sqrt(N) ) ) => O(sqrt(N)) since n is very small

Last edit: 2016-06-09 17:30:17
minhthai: 2016-02-15 15:46:44

very nice problem :) very creative :D

Shashank Tiwari: 2015-12-12 21:58:53

Question can be restated as :

Given a number 'N' , we need to find minimum number of divisors of N such that :

1 ) N = D_1 X D_2 X ...... X D_i (Here we have N as product of 'i' divisors)
2) The count of such divisors used i.e. here it is 'i' should be minimum.
3) There should not be no perfect square which should divide any of these above divisors.
4) Hence 1 is not allowed to be considered as any divisor because of point (3).

Example :
Lets take n =24 .
We can have :

1) 24 = 24 but 4 divides 24 and 4 is perfect square . So , Rejected.
2) 24= 12 X 2 but 4 again divides 12 so , this is also rejected.
3) 24 = 6 X 4 ; This is also rejected as 4 divides 4.
4) 24 = 6 X 2 X 2 ; Now this is acceptable. And this is what we will find that is minimum such possible divisors used satisfying above conditions so mentioned. Hence ans for 24 is 3.

Lets take another example. N= 7.

Here 7=7 is satisfied. So ans =1.

Lets take another example . N=6.

6=6 ; so ans =1.

Lets take another example . N=25.

Here 25 =25 cannot be taken as 25 itself divides 25 and is a perfect square. But 25 = 5 X 5 can be taken . Hence ans = 2.

Lets take N=44 , then 44 = 22 X2 , hence ans =2 . Note that 44 = 4 X 11 is not valid. Also , 44 = 11 X 2 X 2 is long and not of minimum length.

Hope this helps.

ASHUTOSH DWIVEDI: 2015-10-29 16:41:35

Last edit: 2015-11-07 20:31:21
:.Mohib.:: 2015-08-03 20:53:20

Great...!!

Madhav: 2015-03-29 14:08:14

good concept!!

Malinga: 2015-01-09 09:32:09

Sieve+fast I/O...AC in 1.19 sec

Anubhav Balodhi : 2014-12-30 09:35:03

Mathematical one ^_^

BLANKRK: 2014-06-25 22:40:56

nice !!! :)

abhishek nagpal: 2013-09-01 12:03:17

what will be the answer for 44?
2 or 3?


Added by:Varun Jalan
Date:2010-12-13
Time limit:0.274s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem, ICPC Asia regionals, Amritapuri 2010