Given an array of elements find all the prime factors of the LCM of the given numbers.
Example 1:
Input:
N = 8
Arr = {1 , 2, 3, 4, 5, 6, 7, 8}
Output: 2 3 5 7
Explaination: LCM of N elements is 840 
and 840 = 2*2*2*3*5*7.so prime factors 
would be 2, 3, 5, 7.
Example 2:
Input:
N = 4
Arr = {20, 10, 15, 60}
Output: 2 3 5
Explaination: LCM of N elements is 60
and 60 = 2*2*3*5.so prime factors
would be 2, 3, 5.
Your Task:
You don't need to read input or print anything. Your task is to complete the function primeFactorLcm() which takes the array Arr[] and its size N as input parameters and returns all the prime factors of the LCM of the given numbers.
Expected Time Complexity: O(Nsqrt(max(Arr_{i}))
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{4}
1 ≤ Arr_{i} ≤ 10^{4 }where 0≤i<N

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:

    def primeFactorLcm(self, Arr, N):

        # code here

Solutions:
class Solution:

	def lcm(self, a, b):
		from math import gcd
		return a * b // gcd(a, b)

	def primeFactorLcm(self, Arr, N):
		lc = Arr[0]
		lis = []
		for i in Arr:
			lc = self.lcm(lc, i)
		d = 2
		while lc >= d:
			if lc % d == 0:
				while lc % d == 0:
					lc //= d
				lis.append(d)
			d += 1
		return lis


import math
MAX = 10000
primes = []

def sieve_of_sundaram():
	n = MAX
	new_n = int(n - 1 // 2)
	marked = [False] * (new_n + 100)
	for i in range(1, new_n + 1):
		j = i
		while i + j + 2 * i * j <= new_n:
			marked[i + j + 2 * i * j] = True
			j += 1
	primes.append(2)
	for i in range(1, new_n + 1):
		if marked[i] == False:
			primes.append(2 * i + 1)

class Solution:

	def primeFactorLcm(self, arr, n):
		sieve_of_sundaram()
		factors = [0] * 10000
		for i in range(n):
			num = arr[i]
			root = int(math.sqrt(num))
			j = 0
			while primes[j] <= root:
				if num % primes[j] == 0:
					while num % primes[j] == 0:
						num = int(num / primes[j])
					factors[primes[j]] = 1
				j += 1
			if num > 1:
				factors[num] = 1
		ans = []
		if factors[2] == 1:
			ans.append(2)
		for i in range(3, MAX + 1, 2):
			if factors[i] == 1:
				ans.append(i)
		return ans