| 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
|
||||||
|
2022-08-17 10:01:14 [Rampage] Blue.Mary
@nayeem2021: It's possible that your ability of reading and understanding problem statement has some problem. |
||||||
|
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. |
||||||
|
2020-07-11 10:36:45 Shubham Jadhav
Sounds intimidating, but is really easy |
||||||
|
2020-06-23 10:42:47
why i got WA? i am new in SPOJ.in my solution,first i find out the factorization of prime of n.then count the large fruquency of a prime number.but i got WA. |
||||||
|
2019-10-16 12:24:39
hi |
||||||
|
2019-06-18 20:55:52
prime factorization + map -- AC in 0.19s |
||||||
|
2019-05-29 08:11:50
AC in 1st attempt & also 0.00 sec :) |
||||||
|
2018-11-21 11:46:47
intimidating one ! |
||||||
|
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 |
||||||
|
2016-02-15 15:46:44 minhthai
very nice problem :) very creative :D |
||||||
RSS