Find the Nth term divisible by a or b or c | Function to return gcd of a and b ; Function to return the lcm of a and b ; Function to return the count of numbers from 1 to num which are divisible by a , b or c ; Calculate number of terms divisible by a and by b and by c then , remove the terms which is are divisible by both a and b , both b and c , both c and a and then add which are divisible by a and b and c ; Function to find the nth term divisible by a , b or c by using binary search ; Set low to 1 and high to max ( a , b , c ) * n ; If the current term is less than n then we need to increase low to mid + 1 ; If current term is greater than equal to n then high = mid ; Driver code
def gcd ( a , b ) : NEW_LINE INDENT if ( a == 0 ) : NEW_LINE INDENT return b NEW_LINE DEDENT return gcd ( b % a , a ) NEW_LINE DEDENT def lcm ( a , b ) : NEW_LINE INDENT return ( ( a * b ) // gcd ( a , b ) ) NEW_LINE DEDENT def divTermCount ( a , b , c , num ) : NEW_LINE INDENT return ( ( num // a ) + ( num // b ) + ( num // c ) - ( num // lcm ( a , b ) ) - ( num // lcm ( b , c ) ) - ( num // lcm ( a , c ) ) + ( num // lcm ( a , lcm ( b , c ) ) ) ) NEW_LINE DEDENT def findNthTerm ( a , b , c , n ) : NEW_LINE INDENT low = 1 NEW_LINE high = 10 ** 9 NEW_LINE mid = 0 NEW_LINE while ( low < high ) : NEW_LINE INDENT mid = low + ( high - low ) // 2 NEW_LINE if ( divTermCount ( a , b , c , mid ) < n ) : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT high = mid NEW_LINE DEDENT DEDENT return low NEW_LINE DEDENT a = 2 NEW_LINE b = 3 NEW_LINE c = 5 NEW_LINE n = 10 NEW_LINE print ( findNthTerm ( a , b , c , n ) ) NEW_LINE