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 is 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
function gcd ( a , b ) { if ( a == 0 ) return b ; return gcd ( b % a , a ) ; } function divTermCount ( a , b , lcm , num ) { return parseInt ( num / a ) + parseInt ( num / b ) - parseInt ( num / lcm ) ; } function findNthTerm ( a , b , n ) { var low = 1 , high = Number . MAX_VALUE , mid ; var lcm = parseInt ( ( a * b ) / gcd ( a , b ) ) ; while ( low < high ) { mid = low + parseInt ( ( high - low ) / 2 ) ; if ( divTermCount ( a , b , lcm , mid ) < n ) low = mid + 1 ; else high = mid ; } return low ; } var a = 2 , b = 5 , n = 10 ; document . write ( findNthTerm ( a , b , n ) ) ;