| 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 test case, output the smallest number of square-free factors.
Constraints
T ≤ 104
2 ≤ N ≤ 106
Example
Input: 2 6 8 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
|
||||||
|
2025-03-18 19:01:58
hmm i wonder if the frequencies of the prime factors have anything to do with the answer. if you are getting wrong answer and don't have any clue where to start. start with 36 Last edit: 2025-03-18 19:04:37 |
||||||
|
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 |
||||||
RSS