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 trying the problem, he turned to you for help. He believes that you can help him solve the problem.
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.
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.
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
|Added by:||Nikunj Jain|
|Cluster:||Cube (Intel Pentium G860 3GHz)|
|Languages:||All except: SCM chicken|
It costed me many WA's before which i understood my algo was not better for this question
is there a space after Case i: and then the no of prime factors
AC after lots of WAs :)
i chose this one to be my 150th...teaches some good mathematical concepts...!! :)
200th to solve this problem.
got AC without precomputing primes using or sieve or something.....
The time limit is appropriate. It prohibits a naive solution, and accepts the solutions of non-C/C++ languages.
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:
TLE using naive algo...
Time Limit is too relaxed,Should be around 4-5 sec.Nice question anyways.