Program to find Nth term divisible by a or b | Python 3 program to find nth term divisible by a or b ; Function to return gcd of a and b ; Function to calculate how many numbers from 1 to num are divisible by a or b ; calculate number of terms divisible by a and by b then , remove the terms which are divisible by both a and b ; Binary search to find the nth term divisible by a or b ; set low to 1 and high to max ( a , b ) * n , here we have taken high as 10 ^ 18 ; 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
import sys NEW_LINE 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 divTermCount ( a , b , lcm , num ) : NEW_LINE INDENT return num // a + num // b - num // lcm NEW_LINE DEDENT def findNthTerm ( a , b , n ) : NEW_LINE INDENT low = 1 ; high = sys . maxsize NEW_LINE lcm = ( a * b ) // gcd ( a , b ) NEW_LINE while low < high : NEW_LINE INDENT mid = low + ( high - low ) // 2 NEW_LINE if divTermCount ( a , b , lcm , 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 ; b = 5 ; n = 10 NEW_LINE print ( findNthTerm ( a , b , n ) ) NEW_LINE