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
|
tashfiq_taif_1:
2024-01-26 13:47:35
good problem Last edit: 2024-01-26 13:48:04 |
|
tarun_28:
2020-10-03 13:13:44
Sieve + prime factorisation + set |
|
nadstratosfer:
2018-01-15 14:23:02
Testcases have a certain property that one method seems to handle particularly well. In my case got down from 1.10s to 0.10s in Python albeit I can imagine cases where it would yield no gain at all. On the other hand got TLE with an algo I was quite positive to speed my code up. Nice to run into a problem where you can get ahead by some hacking rather than ugly optimizations, also kudos for TL that enables it. |
|
hodobox:
2015-12-20 19:36:53
TLE with O(sqrt(a)), AC 0.14 with sieve up to 10^6. |
|
:.Mohib.::
2015-07-17 01:10:19
Good one... :) |
|
Aditya Kumar:
2015-05-19 05:25:05
It costed me many WA's before which i understood my algo was not better for this question
|
|
black MaMbA:
2014-10-17 21:48:55
is there a space after Case i: and then the no of prime factors |
|
||N0VICE||:
2014-07-01 20:48:51
AC after lots of WAs :) |
|
Akb:
2013-03-29 04:16:29
i chose this one to be my 150th...teaches some good mathematical concepts...!! :) |
|
(^_^):
2013-03-16 08:05:51
200th to solve this problem.
|
| 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