Distinct Prime Factors of an Array | Function to return an array of prime numbers upto n using Sieve of Eratosthenes ; Function to return distinct prime factors from the given array ; Creating an empty array to store distinct prime factors ; Iterating through all the prime numbers and check if any of the prime numbers is a factor of the given input array ; Driver code ; Finding prime numbers upto 10000 using Sieve of Eratosthenes
def sieve ( n ) : NEW_LINE INDENT prime = [ True ] * ( n + 1 ) NEW_LINE p = 2 NEW_LINE while ( p * p <= n ) : NEW_LINE INDENT if ( prime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * p , n + 1 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT allPrimes = [ x for x in range ( 2 , n ) if prime [ x ] ] NEW_LINE return allPrimes NEW_LINE DEDENT def distPrime ( arr , allPrimes ) : NEW_LINE INDENT list1 = list ( ) NEW_LINE for i in allPrimes : NEW_LINE INDENT for j in arr : NEW_LINE INDENT if ( j % i == 0 ) : NEW_LINE INDENT list1 . append ( i ) NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT return list1 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT allPrimes = sieve ( 10000 ) NEW_LINE arr = [ 15 , 30 , 60 ] NEW_LINE ans = distPrime ( arr , allPrimes ) NEW_LINE print ( ans ) NEW_LINE DEDENT