Sphere Online Judge

SPOJ Problem Set (classical)

11103. PrimeFactorofLCM

Problem code: MAIN12B


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 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


Added by:Nikunj Jain
Date:2012-03-15
Time limit:10s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All
Resource:Vaibhav Mittal

hide comments
2014-07-01 20:48:51 ||N0VICE||
AC after lots of WAs :)
2013-03-29 04:16:29 Aaquib Javed
i chose this one to be my 150th...teaches some good mathematical concepts...!! :)
2013-03-16 08:05:51 (^_^)
200th to solve this problem.
Easy one.
2013-01-05 07:10:31 Aditya Pande
got AC without precomputing primes using or sieve or something.....
2012-11-20 07:28:00 Paul Draper
The time limit is appropriate. It prohibits a naive solution, and accepts the solutions of non-C/C++ languages.
2012-10-09 20:36:19 Nic Roets
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:

When I run it on the test case below, it took 65s on my Pentium M 1.7GHz.

100
100
999999999989 ...
100
(Some more prime numbers exceeding 10^11)
...
2012-07-16 12:52:39 Bharath Reddy
TLE using naive algo...
Worst case running for 34 sec on my comp

Last edit: 2012-07-16 12:53:10
2012-06-29 08:47:24 PubLic_AvenGeR
Time Limit is too relaxed,Should be around 4-5 sec.Nice question anyways.
2012-06-03 12:09:14 15972125841321
can someone plz tell me where i m getting wa... my sub id 7083656
2012-04-06 16:21:13 fitcat
This question is for students who have just started programming? Those students are all genius :)


Last edit: 2012-04-06 16:22:34
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.