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.
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 nondecreasing 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
hodobox:
20151220 19:36:53
TLE with O(sqrt(a)), AC 0.14 with sieve up to 10^6. 

:.Mohib.::
20150717 01:10:19
Good one... :) 

Aditya Kumar:
20150519 05:25:05
It costed me many WA's before which i understood my algo was not better for this question


black MaMbA:
20141017 21:48:55
is there a space after Case i: and then the no of prime factors 

N0VICE:
20140701 20:48:51
AC after lots of WAs :) 

Akb:
20130329 04:16:29
i chose this one to be my 150th...teaches some good mathematical concepts...!! :) 

(^_^):
20130316 08:05:51
200th to solve this problem.


Aditya Pande:
20130105 07:10:31
got AC without precomputing primes using or sieve or something..... 

Paul Draper:
20121120 07:28:00
The time limit is appropriate. It prohibits a naive solution, and accepts the solutions of nonC/C++ languages. 

Nic Roets:
20121009 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:

Added by:  Nikunj Jain 
Date:  20120315 
Time limit:  1.193s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Vaibhav Mittal 