Find the row whose product has maximum count of prime factors | Python3 implementation to find the row whose product has maximum number of prime factors ; function for SieveOfEratosthenes ; Create a boolean array " isPrime [ 0 . . N ] " and initialize all entries it as true . A value in isPrime [ i ] will finally be false if i is not a prime , else true . ; check if isPrime [ p ] is not changed ; Update all multiples of p ; Print all isPrime numbers ; function to display the answer ; function to Count the row number of divisors in particular row multiplication ; Find count of occurrences of each prime factor ; Compute count of all divisors ; Update row number if factors of this row is max ; Clearing map to store prime factors for next row ; Driver code
N = 3 NEW_LINE M = 5 NEW_LINE Large = int ( 1e6 ) ; NEW_LINE prime = [ ] ; NEW_LINE def SieveOfEratosthenes ( ) : NEW_LINE INDENT isPrime = [ True ] * ( Large + 1 ) ; NEW_LINE for p in range ( 2 , int ( Large ** ( 1 / 2 ) ) ) : NEW_LINE INDENT if ( isPrime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * 2 , Large + 1 , p ) : NEW_LINE INDENT isPrime [ i ] = False ; NEW_LINE DEDENT DEDENT DEDENT for p in range ( 2 , Large + 1 ) : NEW_LINE INDENT if ( isPrime [ p ] ) : NEW_LINE INDENT prime . append ( p ) ; NEW_LINE DEDENT DEDENT DEDENT def Display ( arr , row ) : NEW_LINE INDENT for i in range ( M ) : NEW_LINE INDENT print ( arr [ row ] [ i ] , end = " ▁ " ) ; NEW_LINE DEDENT DEDENT def countDivisorsMult ( arr ) : NEW_LINE INDENT mp = { } ; NEW_LINE row_no = 0 ; max_factor = 0 ; NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( M ) : NEW_LINE INDENT no = arr [ i ] [ j ] NEW_LINE for k in range ( len ( prime ) ) : NEW_LINE INDENT while ( no > 1 and no % prime [ k ] == 0 ) : NEW_LINE INDENT no //= prime [ k ] ; NEW_LINE if prime [ k ] not in mp : NEW_LINE INDENT mp [ prime [ k ] ] = 0 NEW_LINE DEDENT mp [ prime [ k ] ] += 1 ; NEW_LINE DEDENT if ( no == 1 ) : NEW_LINE INDENT break ; NEW_LINE DEDENT DEDENT DEDENT res = 1 ; NEW_LINE for it in mp : NEW_LINE INDENT res *= mp [ it ] ; NEW_LINE DEDENT if ( max_factor < res ) : NEW_LINE INDENT row_no = i ; NEW_LINE max_factor = res ; NEW_LINE DEDENT mp . clear ( ) ; NEW_LINE DEDENT Display ( arr , row_no ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ [ 1 , 2 , 3 , 10 , 23 ] , [ 4 , 5 , 6 , 7 , 8 ] , [ 7 , 8 , 9 , 15 , 45 ] ] ; NEW_LINE SieveOfEratosthenes ( ) ; NEW_LINE countDivisorsMult ( arr ) ; NEW_LINE DEDENT