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
hide comments
[Rampage] Blue.Mary:
2022-08-17 10:01:14
@nayeem2021: It's possible that your ability of reading and understanding problem statement has some problem. |
|
nayeem2021:
2022-08-14 08:15:30
The problem statement should be clarified and re-written again. Very pathetic description. It's programming problem not some riddle by a Riddler. |
|
Shubham Jadhav:
2020-07-11 10:36:45
Sounds intimidating, but is really easy |
|
shakib19:
2020-06-23 10:42:47
why i got WA?
|
|
zihadboss:
2019-10-16 12:24:39
hi |
|
towhid1zaman:
2019-06-18 20:55:52
prime factorization + map -- AC in 0.19s |
|
roni_roy18:
2019-05-29 08:11:50
AC in 1st attempt & also 0.00 sec :)
|
|
koushiq:
2018-11-21 11:46:47
intimidating one ! |
|
karthik1997:
2016-06-09 17:27:11
Nice Que :) AC 0.00s in first Go :D
|
|
minhthai:
2016-02-15 15:46:44
very nice problem :) very creative :D |
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 |