# Program to find Nth term divisible by a or b

Given two integers and . The task is to find the Nth term which is divisible by either of or .**Examples :**

Input: a = 2, b = 5, N = 10Output: 16Input: a = 3, b = 7, N = 25Output: 57

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

**Naive Approach:** A simple approach is to traverse over all the terms starting from 1 until we find the desired Nth term which is divisible by either of or . This solution has time complexity of O(N).**Efficient Approach:** The idea is to use Binary search. Here we can calculate how many numbers from 1 to are divisible by either a or b by using formula:

All the multiples of lcm(a, b) will be divisible by both and so we need to remove these terms. Now if the number of divisible terms is less than N we will increase the low position of binary search otherwise decrease high until number of divisible terms is equal to N.

Below is the implementation of the above idea :

## C++

`// C++ program to find nth term` `// divisible by a or b` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to return` `// gcd of a and b` `int` `gcd(` `int` `a, ` `int` `b)` `{` ` ` `if` `(a == 0)` ` ` `return` `b;` ` ` `return` `gcd(b % a, a);` `}` `// Function to calculate how many numbers` `// from 1 to num are divisible by a or b` `int` `divTermCount(` `int` `a, ` `int` `b, ` `int` `lcm, ` `int` `num)` `{` ` ` `// calculate number of terms divisible by a and` ` ` `// by b then, remove the terms which is are` ` ` `// divisible by both a and b` ` ` `return` `num / a + num / b - num / lcm;` `}` `// Binary search to find the nth term` `// divisible by a or b` `int` `findNthTerm(` `int` `a, ` `int` `b, ` `int` `n)` `{` ` ` `// set low to 1 and high to max(a, b)*n, here` ` ` `// we have taken high as 10^18` ` ` `int` `low = 1, high = INT_MAX, mid;` ` ` `int` `lcm = (a * b) / gcd(a, b);` ` ` `while` `(low < high) {` ` ` `mid = low + (high - low) / 2;` ` ` `// if the current term is less than` ` ` `// n then we need to increase low` ` ` `// to mid + 1` ` ` `if` `(divTermCount(a, b, lcm, mid) < n)` ` ` `low = mid + 1;` ` ` `// if current term is greater than equal to` ` ` `// n then high = mid` ` ` `else` ` ` `high = mid;` ` ` `}` ` ` `return` `low;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `a = 2, b = 5, n = 10;` ` ` `cout << findNthTerm(a, b, n) << endl;` ` ` `return` `0;` `}` |

## Java

`// Java program to find nth term` `// divisible by a or b` `class` `GFG` `{` `// Function to return` `// gcd of a and b` `static` `int` `gcd(` `int` `a, ` `int` `b)` `{` ` ` `if` `(a == ` `0` `)` ` ` `return` `b;` ` ` `return` `gcd(b % a, a);` `}` `// Function to calculate how many numbers` `// from 1 to num are divisible by a or b` `static` `int` `divTermCount(` `int` `a, ` `int` `b,` ` ` `int` `lcm, ` `int` `num)` `{` ` ` `// calculate number of terms` ` ` `// divisible by a and by b then,` ` ` `// remove the terms which is are` ` ` `// divisible by both a and b` ` ` `return` `num / a + num / b - num / lcm;` `}` `// Binary search to find the` `// nth term divisible by a or b` `static` `int` `findNthTerm(` `int` `a, ` `int` `b, ` `int` `n)` `{` ` ` `// set low to 1 and high to max(a, b)*n, ` ` ` `// here we have taken high as 10^18` ` ` `int` `low = ` `1` `, high = Integer.MAX_VALUE, mid;` ` ` `int` `lcm = (a * b) / gcd(a, b);` ` ` `while` `(low < high)` ` ` `{` ` ` `mid = low + (high - low) / ` `2` `;` ` ` `// if the current term is less` ` ` `// than n then we need to increase` ` ` `// low to mid + 1` ` ` `if` `(divTermCount(a, b, lcm, mid) < n)` ` ` `low = mid + ` `1` `;` ` ` `// if current term is greater` ` ` `// than equal to n then high = mid` ` ` `else` ` ` `high = mid;` ` ` `}` ` ` `return` `low;` `}` `// Driver code` `public` `static` `void` `main (String[] args)` `{` ` ` `int` `a = ` `2` `, b = ` `5` `, n = ` `10` `;` ` ` `System.out.println(findNthTerm(a, b, n));` `}` `}` `// This code is contributed by Smitha` |

## Python3

`# Python 3 program to find nth term` `# divisible by a or b` `import` `sys` `# Function to return gcd of a and b` `def` `gcd(a, b):` ` ` `if` `a ` `=` `=` `0` `:` ` ` `return` `b` ` ` `return` `gcd(b ` `%` `a, a)` `# Function to calculate how many numbers` `# from 1 to num are divisible by a or b` `def` `divTermCount(a, b, lcm, num):` ` ` `# calculate number of terms divisible` ` ` `# by a and by b then, remove the terms` ` ` `# which are divisible by both a and b` ` ` `return` `num ` `/` `/` `a ` `+` `num ` `/` `/` `b ` `-` `num ` `/` `/` `lcm` `# Binary search to find the nth term` `# divisible by a or b` `def` `findNthTerm(a, b, n):` ` ` `# set low to 1 and high to max(a, b)*n,` ` ` `# here we have taken high as 10^18` ` ` `low ` `=` `1` `; high ` `=` `sys.maxsize` ` ` `lcm ` `=` `(a ` `*` `b) ` `/` `/` `gcd(a, b)` ` ` `while` `low < high:` ` ` `mid ` `=` `low ` `+` `(high ` `-` `low) ` `/` `/` `2` ` ` `# if the current term is less` ` ` `# than n then we need to increase ` ` ` `# low to mid + 1` ` ` `if` `divTermCount(a, b, lcm, mid) < n:` ` ` `low ` `=` `mid ` `+` `1` ` ` `# if current term is greater` ` ` `# than equal to n then high = mid` ` ` `else` `:` ` ` `high ` `=` `mid` ` ` `return` `low` `# Driver code` `a ` `=` `2` `; b ` `=` `5` `; n ` `=` `10` `print` `(findNthTerm(a, b, n))` `# This code is contributed by Shrikant13` |

## C#

`// C# program to find nth term` `// divisible by a or b` `using` `System;` `class` `GFG` `{` `// Function to return gcd of a and b` `static` `int` `gcd(` `int` `a, ` `int` `b)` `{` ` ` `if` `(a == 0)` ` ` `return` `b;` ` ` `return` `gcd(b % a, a);` `}` `// Function to calculate how many numbers` `// from 1 to num are divisible by a or b` `static` `int` `divTermCount(` `int` `a, ` `int` `b,` ` ` `int` `lcm, ` `int` `num)` `{` ` ` `// calculate number of terms` ` ` `// divisible by a and by b then,` ` ` `// remove the terms which is are` ` ` `// divisible by both a and b` ` ` `return` `num / a + num / b - num / lcm;` `}` `// Binary search to find the` `// nth term divisible by a or b` `static` `int` `findNthTerm(` `int` `a, ` `int` `b, ` `int` `n)` `{` ` ` `// set low to 1 and high to max(a, b)*n,` ` ` `// here we have taken high as 10^18` ` ` `int` `low = 1, high = ` `int` `.MaxValue, mid;` ` ` `int` `lcm = (a * b) / gcd(a, b);` ` ` `while` `(low < high)` ` ` `{` ` ` `mid = low + (high - low) / 2;` ` ` `// if the current term is less` ` ` `// than n then we need to increase` ` ` `// low to mid + 1` ` ` `if` `(divTermCount(a, b, lcm, mid) < n)` ` ` `low = mid + 1;` ` ` `// if current term is greater` ` ` `// than equal to n then high = mid` ` ` `else` ` ` `high = mid;` ` ` `}` ` ` `return` `low;` `}` `// Driver code` `static` `public` `void` `Main ()` `{` ` ` `int` `a = 2, b = 5, n = 10;` ` ` `Console.WriteLine(findNthTerm(a, b, n));` `}` `}` `// This code is contributed by Sach_Code` |

## Javascript

`<script>` `// JavaScript program to find nth term` `// divisible by a or b` `// Function to return` `// gcd of a and b` `function` `gcd(a , b)` `{` ` ` `if` `(a == 0)` ` ` `return` `b;` ` ` `return` `gcd(b % a, a);` `}` `// Function to calculate how many numbers` `// from 1 to num are divisible by a or b` `function` `divTermCount(a , b, lcm , num)` `{` ` ` `// calculate number of terms` ` ` `// divisible by a and by b then,` ` ` `// remove the terms which is are` ` ` `// divisible by both a and b` ` ` `return` `parseInt(num / a) +` ` ` `parseInt(num / b) - parseInt(num / lcm);` `}` `// Binary search to find the` `// nth term divisible by a or b` `function` `findNthTerm(a , b , n)` `{` ` ` `// set low to 1 and high to max(a, b)*n, ` ` ` `// here we have taken high as 10^18` ` ` `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 the current term is less` ` ` `// than n then we need to increase` ` ` `// low to mid + 1` ` ` `if` `(divTermCount(a, b, lcm, mid) < n)` ` ` `low = mid + 1;` ` ` `// if current term is greater` ` ` `// than equal to n then high = mid` ` ` `else` ` ` `high = mid;` ` ` `}` ` ` `return` `low;` `}` `// Driver code` `var` `a = 2, b = 5, n = 10;` `document.write(findNthTerm(a, b, n));` `// This code is contributed by Amit Katiyar` `</script>` |

**Output:**

16