Find a number that divides maximum array elements | Python3 program to find a number that divides maximum array elements ; stores smallest prime factor for every number ; Calculating SPF ( Smallest Prime Factor ) for every number till MAXN . Time Complexity : O ( nloglogn ) ; marking smallest prime factor for every number to be itself . ; separately marking spf for every even number as 2 ; checking if i is prime ; marking SPF for all numbers divisible by i ; marking spf [ j ] if it is not previously marked ; A O ( log n ) function returning primefactorization by dividing by smallest prime factor at every step ; Function to find a number that divides maximum array elements ; precalculating Smallest Prime Factor ; Hash to store frequency of each divisors ; Traverse the array and get spf of each element ; calling getFactorization function ; Review set view ; Driver Code
import math as mt NEW_LINE MAXN = 100001 NEW_LINE spf = [ 0 for i in range ( MAXN ) ] NEW_LINE def sieve ( ) : NEW_LINE INDENT spf [ 1 ] = 1 NEW_LINE for i in range ( 2 , MAXN ) : NEW_LINE INDENT spf [ i ] = i NEW_LINE DEDENT for i in range ( 4 , MAXN , 2 ) : NEW_LINE INDENT spf [ i ] = 2 NEW_LINE DEDENT for i in range ( 3 , mt . ceil ( mt . sqrt ( MAXN + 1 ) ) ) : NEW_LINE INDENT if ( spf [ i ] == i ) : NEW_LINE INDENT for j in range ( 2 * i , MAXN , i ) : NEW_LINE INDENT if ( spf [ j ] == j ) : NEW_LINE INDENT spf [ j ] = i NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT def getFactorization ( x ) : NEW_LINE INDENT ret = list ( ) NEW_LINE while ( x != 1 ) : NEW_LINE INDENT temp = spf [ x ] NEW_LINE ret . append ( temp ) NEW_LINE while ( x % temp == 0 ) : NEW_LINE INDENT x = x // temp NEW_LINE DEDENT DEDENT return ret NEW_LINE DEDENT def maxElement ( A , n ) : NEW_LINE INDENT sieve ( ) NEW_LINE m = dict ( ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT p = getFactorization ( A [ i ] ) NEW_LINE for i in range ( len ( p ) ) : NEW_LINE INDENT if p [ i ] in m . keys ( ) : NEW_LINE INDENT m [ p [ i ] ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT m [ p [ i ] ] = 1 NEW_LINE DEDENT DEDENT DEDENT cnt = 0 NEW_LINE ans = 10 ** 9 + 7 NEW_LINE for i in m : NEW_LINE INDENT if ( m [ i ] >= cnt ) : NEW_LINE INDENT cnt = m [ i ] NEW_LINE if ans > i : NEW_LINE INDENT ans = i NEW_LINE DEDENT else : NEW_LINE INDENT ans = ans NEW_LINE DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT A = [ 2 , 5 , 10 ] NEW_LINE n = len ( A ) NEW_LINE print ( maxElement ( A , n ) ) NEW_LINE