| Submit | All submissions | Best solutions | Back to list |
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.
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
| Added by: | Varun Jalan |
| Date: | 2010-12-13 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | own problem, ICPC Asia regionals, Amritapuri 2010 |
hide comments
|
||||||
|
2015-12-12 21:58:53 Shashank Tiwari
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. |
||||||
|
2015-08-03 20:53:20 :.Mohib.:
Great...!! |
||||||
|
2015-03-29 14:08:14 Madhav
good concept!! |
||||||
|
2015-01-09 09:32:09 Malinga
Sieve+fast I/O...AC in 1.19 sec |
||||||
|
2014-12-30 09:35:03 Anubhav Balodhi
Mathematical one ^_^ |
||||||
|
2014-06-25 22:40:56 BLANKRK
nice !!! :) |
||||||
|
2013-09-01 12:03:17 abhishek nagpal
what will be the answer for 44? 2 or 3? |
||||||
|
2013-02-05 00:13:02 Spar!k
sieve just makes it slower. sqrt(n) is ok |
||||||
|
2012-12-15 22:04:39 Branfili
@Kennard 2, because 36=6*6 |
||||||
RSS