MAIN12B - PrimeFactorofLCM
Everyone loves Swampy. Swampy the Alligator lives under the city and yearns for a more human like existence. One day Swampy took part in a maths contest to show his supremacy over other his other alligator friends. The task required him to output the prime divisors of the lcm of n numbers a1, a2 ... an. Tired of trying the problem, he turned to you for help. He believes that you can help him solve the problem.
Input
First line of the input contains an integer T, the number of test cases. Then T test cases follow. Each test case consists of a single integer n. Next line contains n integers (space separated), a1, a2 ... an.
Output
For each test case, print Case #X: M where M is the number of prime divisors of lcm(a1, a2 ... an) and then M lines with the prime divisors in non-decreasing order.
Example
Input: 1 8 1 2 3 4 5 6 7 8 Output: Case #1: 4 2 3 5 7
Constraints: T <= 100 1 <= N <= 100 1 <= ai <= 10^12
hide comments
|
Aditya Pande:
2013-01-05 07:10:31
got AC without precomputing primes using or sieve or something..... |
|
Paul Draper:
2012-11-20 07:28:00
The time limit is appropriate. It prohibits a naive solution, and accepts the solutions of non-C/C++ languages. |
|
Nic Roets:
2012-10-09 20:36:19
I use O(sqrt(a)) algorithm and got AC with 2s. I am however convinced that the tests in the judge are not very hard:
|
|
Bharath Reddy:
2012-07-16 12:52:39
TLE using naive algo...
|
|
PubLic_AvenGeR:
2012-06-29 08:47:24
Time Limit is too relaxed,Should be around 4-5 sec.Nice question anyways. |
|
15972125841321:
2012-06-03 12:09:14
can someone plz tell me where i m getting wa... my sub id 7083656 |
|
fitcat:
2012-04-06 16:21:13
This question is for students who have just started programming? Those students are all genius :)
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-03-30 17:29:55
bubble sort O(n^2) + prime sieve O(n) + factorization O(sqrt(n)) = 0.18s :) |
|
Vaibhav Mittal:
2012-03-19 14:10:01
@XeRon!X : Time limit is kept relaxed because this problem was served to students who have just started programming. |
|
XeRoN!X:
2012-03-19 07:51:59
10s is too much.
|
| Added by: | Nikunj Jain |
| Date: | 2012-03-15 |
| Time limit: | 1.193s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Vaibhav Mittal |
RSS