Highest power of 2 that divides the LCM of first N Natural numbers . | Function to find LCM of first N natural numbers ; Initialize result ; Ans contains LCM of 1 , 2 , 3 , . . i after i 'th iteration ; Function to find the highest power of 2 which divides LCM of first n natural numbers ; Find lcm of first N natural numbers ; To store the highest required power of 2 ; Counting number of consecutive zeros from the end in the given binary String ; Driver code
def findlcm ( n ) : NEW_LINE INDENT ans = 1 ; NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT ans = ( ( ( i * ans ) ) // ( __gcd ( i , ans ) ) ) ; NEW_LINE DEDENT return ans ; NEW_LINE DEDENT def highestPower ( n ) : NEW_LINE INDENT lcm = findlcm ( n ) ; NEW_LINE ans = 0 ; NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT x = int ( pow ( 2 , i ) ) ; NEW_LINE if ( lcm % x == 0 ) : NEW_LINE INDENT ans = i ; NEW_LINE DEDENT if ( x > n ) : NEW_LINE INDENT break ; NEW_LINE DEDENT DEDENT return ans ; NEW_LINE DEDENT def __gcd ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a ; NEW_LINE DEDENT else : NEW_LINE INDENT return __gcd ( b , a % b ) ; NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 15 ; NEW_LINE print ( highestPower ( n ) ) ; NEW_LINE DEDENT