# Find and Count total factors of co-prime A or B in a given range 1 to N

Given three integers N, A, B, the task is to find the remainder when the sum of integers which are divisible by either A or B in the range [1, N] is divided by the number of integers in this range.**Note:** The numbers A and B are co-primes. **Examples:**

Input:N = 88, A = 11, B = 8Output:8Explanation:

There are a total of 18 numbers in the range [1, 88] which are divisible by either 8 or 11. They are:

{ 8, 11, 16, 22, 24, 32, 33, 40, 44, 48, 55, 56, 64, 66, 72, 77, 80, 88 }. Therefore, the sum of these numbers is 836. Therefore, 836 % 18 = 8.Input:N = 100, A = 7, B = 19Output:13Explanation:

There are a total of 19 numbers in the range [1, 100] which are divisible by either 7 or 19. They are:

{ 7, 14, 19, 21, 28, 35, 38, 42, 49, 56, 57, 63, 70, 76, 77, 84, 91, 95, 98 }. Therefore, the sum of these numbers is 1020. Therefore, 1020 % 19 = 13.

**Naive Approach:** The naive approach is to run a loop from 1 to N and count all the numbers which are divisible by either A or B while simultaneously adding those numbers in a variable to find its sum. **Time Complexity:** O(N)**Efficient Approach:** Efficient approach is to use the division method.

- By using the division method, the
**count of the numbers**which are**divisible**either by**A**or**B**can be found in the constant time. The idea is to:**Divide N by A**to get the count of numbers divisible by**A**in the range [1, N].**Divide N by B**to get the count of numbers divisible by**B**in the range [1, N].**Divide N by A * B**to get the count of numbers divisible by**both A and B**.**Add**the values obtained in**step 1 and step 2**and**subtract**the value obtained in**step 3**to remove the numbers which have been counted twice.

- Since we are even interested in finding the
**numbers which are divisible**in this range, the idea is to reduce the number of times the conditions are checked by the following way:- Instead of completely relying on one loop, we can use
**two loops**. - One loop is to find the numbers divisible by
**A**. Instead of incrementing the values by 1, we start the loop from A and increment it by A. This reduces the number of comparisons drastically. - Similarly, another loop is used to find the numbers divisible by
**B**. - Since again, there might be repetitions in the numbers, the numbers are stored in a set so that there are no repetitions.

- Instead of completely relying on one loop, we can use
- Once the count and sum of the numbers are found, then directly modulo operation can be applied to compute the final answer.

Below is the implementation of the above approach:

## CPP

`// C++ implementation of the above approach` `#include <algorithm>` `#include <iostream>` `#include <set>` `#define ll long long` `using` `namespace` `std;` `// Function to return the count of numbers` `// which are divisible by both A and B in` `// the range [1, N] in constant time` `ll ` `int` `countOfNum(ll ` `int` `n, ll ` `int` `a, ll ` `int` `b)` `{` ` ` `ll ` `int` `cnt_of_a, cnt_of_b, cnt_of_ab, sum;` ` ` `// Compute the count of numbers divisible by` ` ` `// A in the range [1, N]` ` ` `cnt_of_a = n / a;` ` ` `// Compute the count of numbers divisible by` ` ` `// B in the range [1, N]` ` ` `cnt_of_b = n / b;` ` ` `// Adding the counts which are` ` ` `// divisible by A and B` ` ` `sum = cnt_of_b + cnt_of_a;` ` ` `// The above value might contain repeated` ` ` `// values which are divisible by both` ` ` `// A and B. Therefore, the count of numbers` ` ` `// which are divisible by both A and B are found` ` ` `cnt_of_ab = n / (a * b);` ` ` `// The count computed above is subtracted to` ` ` `// compute the final count` ` ` `sum = sum - cnt_of_ab;` ` ` `return` `sum;` `}` `// Function to return the sum of numbers` `// which are divisible by both A and B` `// in the range [1, N]` `ll ` `int` `sumOfNum(ll ` `int` `n, ll ` `int` `a, ll ` `int` `b)` `{` ` ` `ll ` `int` `i;` ` ` `ll ` `int` `sum = 0;` ` ` `// Set to store the numbers so that the` ` ` `// numbers are not repeated` ` ` `set<ll ` `int` `> ans;` ` ` `// For loop to find the numbers` ` ` `// which are divisible by A and insert` ` ` `// them into the set` ` ` `for` `(i = a; i <= n; i = i + a) {` ` ` `ans.insert(i);` ` ` `}` ` ` `// For loop to find the numbers` ` ` `// which are divisible by A and insert` ` ` `// them into the set` ` ` `for` `(i = b; i <= n; i = i + b) {` ` ` `ans.insert(i);` ` ` `}` ` ` `// For loop to iterate through the set` ` ` `// and find the sum` ` ` `for` `(` `auto` `it = ans.begin();` ` ` `it != ans.end(); it++) {` ` ` `sum = sum + *it;` ` ` `}` ` ` `return` `sum;` `}` `// Driver code` `int` `main()` `{` ` ` `ll ` `int` `N = 88;` ` ` `ll ` `int` `A = 11;` ` ` `ll ` `int` `B = 8;` ` ` `ll ` `int` `count = countOfNum(N, A, B);` ` ` `ll ` `int` `sumofnum = sumOfNum(N, A, B);` ` ` `cout << sumofnum % count << endl;` ` ` `return` `0;` `}` |

## Java

`// Java implementation of the above approach` `import` `java.util.*;` `// Function to return the count of numbers` `// which are divisible by both A and B in` `// the range [1, N] in constant time` `class` `GFG` `{` ` ` `static` `int` `countOfNum( ` `int` `n, ` `int` `a, ` `int` `b)` ` ` `{` ` ` `int` `cnt_of_a, cnt_of_b, cnt_of_ab, sum;` ` ` ` ` `// Compute the count of numbers divisible by` ` ` `// A in the range [1, N]` ` ` `cnt_of_a = n / a;` ` ` ` ` `// Compute the count of numbers divisible by` ` ` `// B in the range [1, N]` ` ` `cnt_of_b = n / b;` ` ` ` ` `// Adding the counts which are` ` ` `// divisible by A and B` ` ` `sum = cnt_of_b + cnt_of_a;` ` ` ` ` `// The above value might contain repeated` ` ` `// values which are divisible by both` ` ` `// A and B. Therefore, the count of numbers` ` ` `// which are divisible by both A and B are found` ` ` `cnt_of_ab = n / (a * b);` ` ` ` ` `// The count computed above is subtracted to` ` ` `// compute the final count` ` ` `sum = sum - cnt_of_ab;` ` ` ` ` `return` `sum;` ` ` `}` ` ` ` ` `// Function to return the sum of numbers` ` ` `// which are divisible by both A and B` ` ` `// in the range [1, N]` ` ` `static` `int` `sumOfNum( ` `int` `n, ` `int` `a, ` `int` `b)` ` ` `{` ` ` `int` `i;` ` ` `int` `sum = ` `0` `;` ` ` ` ` `// Set to store the numbers so that the` ` ` `// numbers are not repeated` ` ` `Set< Integer> ans = ` `new` `HashSet<Integer>();` ` ` ` ` `// For loop to find the numbers` ` ` `// which are divisible by A and insert` ` ` `// them into the set` ` ` `for` `(i = a; i <= n; i = i + a) {` ` ` `ans.add(i);` ` ` `}` ` ` ` ` `// For loop to find the numbers` ` ` `// which are divisible by A and insert` ` ` `// them into the set` ` ` `for` `(i = b; i <= n; i = i + b) {` ` ` `ans.add(i);` ` ` `}` ` ` ` ` `// For loop to iterate through the set` ` ` `// and find the sum` ` ` `for` `(Integer it : ans) {` ` ` `sum = sum + it;` ` ` `}` ` ` ` ` `return` `sum;` ` ` `}` ` ` ` ` `// Driver code` ` ` `public` `static` `void` `main (String []args)` ` ` `{` ` ` `int` `N = ` `88` `;` ` ` `int` `A = ` `11` `;` ` ` `int` `B = ` `8` `;` ` ` ` ` `int` `count = countOfNum(N, A, B);` ` ` `int` `sumofnum = sumOfNum(N, A, B);` ` ` ` ` `System.out.print(sumofnum % count);` ` ` `}` `}` `// This code is contributed by chitranayal ` |

## Python3

`# Python3 implementation of the above approach` `# Function to return the count of numbers` `# which are divisible by both A and B in` `# the range [1, N] in constant time` `def` `countOfNum(n, a, b):` ` ` `cnt_of_a, cnt_of_b, cnt_of_ab, ` `sum` `=` `0` `, ` `0` `, ` `0` `, ` `0` ` ` `# Compute the count of numbers divisible by` ` ` `# A in the range [1, N]` ` ` `cnt_of_a ` `=` `n ` `/` `/` `a` ` ` `# Compute the count of numbers divisible by` ` ` `# B in the range [1, N]` ` ` `cnt_of_b ` `=` `n ` `/` `/` `b` ` ` `# Adding the counts which are` ` ` `# divisible by A and B` ` ` `sum` `=` `cnt_of_b ` `+` `cnt_of_a` ` ` `# The above value might contain repeated` ` ` `# values which are divisible by both` ` ` `# A and B. Therefore, the count of numbers` ` ` `# which are divisible by both A and B are found` ` ` `cnt_of_ab ` `=` `n ` `/` `/` `(a ` `*` `b)` ` ` `# The count computed above is subtracted to` ` ` `# compute the final count` ` ` `sum` `=` `sum` `-` `cnt_of_ab` ` ` `return` `sum` `# Function to return the sum of numbers` `# which are divisible by both A and B` `# in the range [1, N]` `def` `sumOfNum(n, a, b):` ` ` `i ` `=` `0` ` ` `sum` `=` `0` ` ` `# Set to store the numbers so that the` ` ` `# numbers are not repeated` ` ` `ans ` `=` `dict` `()` ` ` `# For loop to find the numbers` ` ` `# which are divisible by A and insert` ` ` `# them into the set` ` ` `for` `i ` `in` `range` `(a, n ` `+` `1` `, a):` ` ` `ans[i] ` `=` `1` ` ` `# For loop to find the numbers` ` ` `# which are divisible by A and insert` ` ` `# them into the set` ` ` `for` `i ` `in` `range` `(b, n ` `+` `1` `, b):` ` ` `ans[i] ` `=` `1` ` ` `# For loop to iterate through the set` ` ` `# and find the sum` ` ` `for` `it ` `in` `ans:` ` ` `sum` `=` `sum` `+` `it` ` ` `return` `sum` `# Driver code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `N ` `=` `88` ` ` `A ` `=` `11` ` ` `B ` `=` `8` ` ` `count ` `=` `countOfNum(N, A, B)` ` ` `sumofnum ` `=` `sumOfNum(N, A, B)` ` ` `print` `(sumofnum ` `%` `count)` `# This code is contributed by mohit kumar 29` |

## C#

`// C# implementation of the above approach` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG` `{` ` ` `// Function to return the count of numbers` ` ` `// which are divisible by both A and B in` ` ` `// the range [1, N] in constant time` ` ` ` ` `static` `int` `countOfNum( ` `int` `n, ` `int` `a, ` `int` `b)` ` ` `{` ` ` `int` `cnt_of_a, cnt_of_b, cnt_of_ab, sum;` ` ` ` ` `// Compute the count of numbers divisible by` ` ` `// A in the range [1, N]` ` ` `cnt_of_a = n / a;` ` ` ` ` `// Compute the count of numbers divisible by` ` ` `// B in the range [1, N]` ` ` `cnt_of_b = n / b;` ` ` ` ` `// Adding the counts which are` ` ` `// divisible by A and B` ` ` `sum = cnt_of_b + cnt_of_a;` ` ` ` ` `// The above value might contain repeated` ` ` `// values which are divisible by both` ` ` `// A and B. Therefore, the count of numbers` ` ` `// which are divisible by both A and B are found` ` ` `cnt_of_ab = n / (a * b);` ` ` ` ` `// The count computed above is subtracted to` ` ` `// compute the readonly count` ` ` `sum = sum - cnt_of_ab;` ` ` ` ` `return` `sum;` ` ` `}` ` ` ` ` `// Function to return the sum of numbers` ` ` `// which are divisible by both A and B` ` ` `// in the range [1, N]` ` ` `static` `int` `sumOfNum( ` `int` `n, ` `int` `a, ` `int` `b)` ` ` `{` ` ` `int` `i;` ` ` `int` `sum = 0;` ` ` ` ` `// Set to store the numbers so that the` ` ` `// numbers are not repeated` ` ` `HashSet< ` `int` `> ans = ` `new` `HashSet<` `int` `>();` ` ` ` ` `// For loop to find the numbers` ` ` `// which are divisible by A and insert` ` ` `// them into the set` ` ` `for` `(i = a; i <= n; i = i + a) {` ` ` `ans.Add(i);` ` ` `}` ` ` ` ` `// For loop to find the numbers` ` ` `// which are divisible by A and insert` ` ` `// them into the set` ` ` `for` `(i = b; i <= n; i = i + b) {` ` ` `ans.Add(i);` ` ` `}` ` ` ` ` `// For loop to iterate through the set` ` ` `// and find the sum` ` ` `foreach` `(` `int` `it ` `in` `ans) {` ` ` `sum = sum + it;` ` ` `}` ` ` ` ` `return` `sum;` ` ` `}` ` ` ` ` `// Driver code` ` ` `public` `static` `void` `Main(String []args)` ` ` `{` ` ` `int` `N = 88;` ` ` `int` `A = 11;` ` ` `int` `B = 8;` ` ` ` ` `int` `count = countOfNum(N, A, B);` ` ` `int` `sumofnum = sumOfNum(N, A, B);` ` ` ` ` `Console.Write(sumofnum % count);` ` ` `}` `}` `// This code is contributed by 29AjayKumar` |

## Javascript

`<script>` `// Javascript implementation of the above approach` ` ` ` ` `// Function to return the count of numbers` ` ` `// which are divisible by both A and B in` ` ` `// the range [1, N] in constant time` ` ` `function` `countOfNum(n,a,b)` ` ` `{` ` ` `let cnt_of_a, cnt_of_b, cnt_of_ab, sum;` ` ` ` ` `// Compute the count of numbers divisible by` ` ` `// A in the range [1, N]` ` ` `cnt_of_a = Math.floor(n / a);` ` ` ` ` `// Compute the count of numbers divisible by` ` ` `// B in the range [1, N]` ` ` `cnt_of_b = Math.floor(n / b);` ` ` ` ` `// Adding the counts which are` ` ` `// divisible by A and B` ` ` `sum = cnt_of_b + cnt_of_a;` ` ` ` ` `// The above value might contain repeated` ` ` `// values which are divisible by both` ` ` `// A and B. Therefore, the count of numbers` ` ` `// which are divisible by both A and B are found` ` ` `cnt_of_ab = Math.floor(n / (a * b));` ` ` ` ` `// The count computed above is subtracted to` ` ` `// compute the final count` ` ` `sum = sum - cnt_of_ab;` ` ` ` ` `return` `sum;` ` ` `}` ` ` ` ` `// Function to return the sum of numbers` ` ` `// which are divisible by both A and B` ` ` `// in the range [1, N]` ` ` `function` `sumOfNum(n,a,b)` ` ` `{` ` ` `let i;` ` ` `let sum = 0;` ` ` ` ` `// Set to store the numbers so that the` ` ` `// numbers are not repeated` ` ` `let ans = ` `new` `Set();` ` ` ` ` `// For loop to find the numbers` ` ` `// which are divisible by A and insert` ` ` `// them into the set` ` ` `for` `(i = a; i <= n; i = i + a) {` ` ` `ans.add(i);` ` ` `}` ` ` ` ` `// For loop to find the numbers` ` ` `// which are divisible by A and insert` ` ` `// them into the set` ` ` `for` `(i = b; i <= n; i = i + b) {` ` ` `ans.add(i);` ` ` `}` ` ` ` ` `// For loop to iterate through the set` ` ` `// and find the sum` ` ` `for` `(let it of ans.values()) {` ` ` `sum = sum + it;` ` ` `}` ` ` ` ` `return` `sum;` ` ` `}` ` ` ` ` `// Driver code` ` ` `let N = 88;` ` ` `let A = 11;` ` ` `let B = 8;` ` ` ` ` `let count = countOfNum(N, A, B);` ` ` `let sumofnum = sumOfNum(N, A, B);` ` ` ` ` `document.write(sumofnum % count);` ` ` ` ` ` ` ` ` `// This code is contributed by rag2127` `</script>` |

**Output:**

8

**Time Complexity Analysis:**

- The time taken to run the for loop to find the numbers which are divisible by A is
**O(N / A)**. - The time taken to run the for loop to find the numbers which are divisible by B is
**O(N / B)**. - Therefore, overall time complexity is
**O(N / A) + O(N / B)**.

**Auxiliary Space: **O(N/A + N/B)