Given two integer numbers, the task is to find count of all common divisors of given numbers?
Examples :
Input : a = 12, b = 24 Output: 6 // all common divisors are 1, 2, 3, // 4, 6 and 12 Input : a = 3, b = 17 Output: 1 // all common divisors are 1 Input : a = 20, b = 36 Output: 3 // all common divisors are 1, 2, 4
It is recommended to refer all divisors of a given number as a prerequisite of this article.
Naive Solution
A simple solution is to first find all divisors of first number and store them in an array or hash. Then find common divisors of second number and store them. Finally print common elements of two stored arrays or hash. The key is that the magnitude of powers of prime factors of a divisor should be equal to the minimum power of two prime factors of a and b.
- Find the prime factors of a using prime factorization.
- Find the count of each prime factor of a and store it in a Hashmap.
- Prime factorize b using distinct prime factors of a.
- Then the total number of divisors would be equal to the product of (count + 1)
of each factor. - count is the minimum of counts of each prime factors of a and b.
- This gives the count of all divisors of a and b.
C++
#include <bits/stdc++.h>
using namespace std;
map<int, int> ma;
void primeFactorize(int a)
{
for(int i = 2; i * i <= a; i += 2)
{
int cnt = 0;
while (a % i == 0)
{
cnt++;
a /= i;
}
ma[i] = cnt;
}
if (a > 1)
{
ma[a] = 1;
}
}
int commDiv(int a, int b)
{
primeFactorize(a);
int res = 1;
for(auto m = ma.begin();
m != ma.end(); m++)
{
int cnt = 0;
int key = m->first;
int value = m->second;
while (b % key == 0)
{
b /= key;
cnt++;
}
res *= (min(cnt, value) + 1);
}
return res;
}
int main()
{
int a = 12, b = 24;
cout << commDiv(a, b) << endl;
return 0;
}
Java
import java.util.*;
import java.io.*;
class GFG {
static HashMap<Integer, Integer> ma = new HashMap<>();
static void primeFactorize(int a)
{
for (int i = 2; i * i <= a; i += 2) {
int cnt = 0;
while (a % i == 0) {
cnt++;
a /= i;
}
ma.put(i, cnt);
}
if (a > 1)
ma.put(a, 1);
}
static int commDiv(int a, int b)
{
primeFactorize(a);
int res = 1;
for (Map.Entry<Integer, Integer> m : ma.entrySet()) {
int cnt = 0;
int key = m.getKey();
int value = m.getValue();
while (b % key == 0) {
b /= key;
cnt++;
}
res *= (Math.min(cnt, value) + 1);
}
return res;
}
public static void main(String args[])
{
int a = 12, b = 24;
System.out.println(commDiv(a, b));
}
}
Python3
import math
ma = {}
def primeFactorize(a):
sqt = int(math.sqrt(a))
for i in range(2, sqt, 2):
cnt = 0
while (a % i == 0):
cnt += 1
a /= i
ma[i] = cnt
if (a > 1):
ma[a] = 1
def commDiv(a, b):
primeFactorize(a)
res = 1
for key, value in ma.items():
cnt = 0
while (b % key == 0):
b /= key
cnt += 1
res *= (min(cnt, value) + 1)
return res
a = 12
b = 24
print(commDiv(a, b))
C#
using System;
using System.Collections.Generic;
class GFG{
static Dictionary<int,
int> ma = new Dictionary<int,
int>();
static void primeFactorize(int a)
{
for(int i = 2; i * i <= a; i += 2)
{
int cnt = 0;
while (a % i == 0)
{
cnt++;
a /= i;
}
ma.Add(i, cnt);
}
if (a > 1)
ma.Add(a, 1);
}
static int commDiv(int a, int b)
{
primeFactorize(a);
int res = 1;
foreach(KeyValuePair<int, int> m in ma)
{
int cnt = 0;
int key = m.Key;
int value = m.Value;
while (b % key == 0)
{
b /= key;
cnt++;
}
res *= (Math.Min(cnt, value) + 1);
}
return res;
}
static void Main()
{
int a = 12, b = 24;
Console.WriteLine(commDiv(a, b));
}
}
Javascript
<script>
let ma = new Map();
function primeFactorize(a)
{
for(let i = 2; i * i <= a; i += 2)
{
let cnt = 0;
while (a % i == 0)
{
cnt++;
a = parseInt(a / i, 10);
}
ma.set(i, cnt);
}
if (a > 1)
{
ma.set(a, 1);
}
}
function commDiv(a,b)
{
primeFactorize(a);
let res = 1;
ma.forEach((values,keys)=>{
let cnt = 0;
let key = keys;
let value = values;
while (b % key == 0)
{
b = parseInt(b / key, 10);
cnt++;
}
res *= (Math.min(cnt, value) + 1);
})
return res;
}
let a = 12, b = 24;
document.write(commDiv(a, b));
</script>
Output:
6
Time Complexity: O(√n log n)
Auxiliary Space: O(n)
Efficient Solution –
A better solution is to calculate the greatest common divisor (gcd) of given two numbers, and then count divisors of that gcd.
C++
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
int commDiv(int a, int b)
{
int n = gcd(a, b);
int result = 0;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
if (n / i == i)
result += 1;
else
result += 2;
}
}
return result;
}
int main()
{
int a = 12, b = 24;
cout << commDiv(a, b);
return 0;
}
Java
class Test {
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
static int commDiv(int a, int b)
{
int n = gcd(a, b);
int result = 0;
for (int i = 1; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
if (n / i == i)
result += 1;
else
result += 2;
}
}
return result;
}
public static void main(String args[])
{
int a = 12, b = 24;
System.out.println(commDiv(a, b));
}
}
Python3
from math import sqrt
def gcd(a, b):
if a == 0:
return b
return gcd(b % a, a)
def commDiv(a, b):
n = gcd(a, b)
result = 0
for i in range(1,int(sqrt(n))+1):
if n % i == 0:
if n/i == i:
result += 1
else:
result += 2
return result
if __name__ == "__main__":
a = 12
b = 24;
print(commDiv(a, b))
C#
using System;
class GFG {
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
static int commDiv(int a, int b)
{
int n = gcd(a, b);
int result = 0;
for (int i = 1; i <= Math.Sqrt(n); i++) {
if (n % i == 0) {
if (n / i == i)
result += 1;
else
result += 2;
}
}
return result;
}
public static void Main(String[] args)
{
int a = 12, b = 24;
Console.Write(commDiv(a, b));
}
}
PHP
<?php
function gcd($a, $b)
{
if ($a == 0)
return $b;
return gcd($b % $a, $a);
}
function commDiv($a, $b)
{
$n = gcd($a, $b);
$result = 0;
for ($i = 1; $i <= sqrt($n);
$i++)
{
if ($n % $i == 0)
{
if ($n / $i == $i)
$result += 1;
else
$result += 2;
}
}
return $result;
}
$a = 12; $b = 24;
echo(commDiv($a, $b));
?>
Javascript
<script>
function gcd(a, b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
function commDiv(a, b)
{
let n = gcd(a, b);
let result = 0;
for (let i = 1; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
if (n / i == i)
result += 1;
else
result += 2;
}
}
return result;
}
let a = 12, b = 24;
document.write(commDiv(a, b));
</script>
Output :
6
Time complexity: O(n1/2) where n is the gcd of two numbers.
Auxiliary Space: O(1)
This article is contributed by Aarti_Rathi and Shashank Mishra ( Gullu ). If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Another Approach:
1. Define a function “gcd” that takes two integers “a” and “b” and returns their greatest common divisor (GCD) using the Euclidean algorithm.
2. Define a function “count_common_divisors” that takes two integers “a” and “b” and counts the number of common divisors of “a” and “b” using their GCD.
3. Calculate the GCD of “a” and “b” using the “gcd” function.
4. Initialize a counter “count” to 0.
5. Loop through all possible divisors of the GCD of “a” and “b” from 1 to the square root of the GCD.
6. If the current divisor divides the GCD evenly, increment the counter by 2 (because both “a” and “b” are divisible by the divisor).
7. If the square of the current divisor equals the GCD, decrement the counter by 1 (because we’ve already counted this divisor once).
8. Return the final count of common divisors.
9. In the main function, define two integers “a” and “b” and call the “count_common_divisors” function with these integers.
10. Print the number of common divisors of “a” and “b” using the printf function.
C
#include <stdio.h>
int gcd(int a, int b) {
if(b == 0) {
return a;
}
return gcd(b, a % b);
}
int count_common_divisors(int a, int b) {
int gcd_ab = gcd(a, b);
int count = 0;
for(int i = 1; i * i <= gcd_ab; i++) {
if(gcd_ab % i == 0) {
count += 2;
if(i * i == gcd_ab) {
count--;
}
}
}
return count;
}
int main() {
int a = 12;
int b = 18;
int common_divisors = count_common_divisors(a, b);
printf("The number of common divisors of %d and %d is %d.n", a, b, common_divisors);
return 0;
}
C++
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
if(b == 0) {
return a;
}
return gcd(b, a % b);
}
int count_common_divisors(int a, int b) {
int gcd_ab = gcd(a, b);
int count = 0;
for(int i = 1; i * i <= gcd_ab; i++) {
if(gcd_ab % i == 0) {
count += 2;
if(i * i == gcd_ab) {
count--;
}
}
}
return count;
}
int main() {
int a = 12;
int b = 18;
int common_divisors = count_common_divisors(a, b);
cout<<"The number of common divisors of "<<a<<" and "<<b<<" is "<<common_divisors<<"."<<endl;
return 0;
}
Java
import java.util.*;
public class Main {
public static int gcd(int a, int b) {
if(b == 0) {
return a;
}
return gcd(b, a % b);
}
public static int countCommonDivisors(int a, int b) {
int gcd_ab = gcd(a, b);
int count = 0;
for(int i = 1; i * i <= gcd_ab; i++) {
if(gcd_ab % i == 0) {
count += 2;
if(i * i == gcd_ab) {
count--;
}
}
}
return count;
}
public static void main(String[] args) {
int a = 12;
int b = 18;
int commonDivisors = countCommonDivisors(a, b);
System.out.println("The number of common divisors of " + a + " and " + b + " is " + commonDivisors + ".");
}
}
Python3
import math
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
def count_common_divisors(a, b):
gcd_ab = gcd(a, b)
count = 0
for i in range(1, int(math.sqrt(gcd_ab)) + 1):
if gcd_ab % i == 0:
count += 2
if i * i == gcd_ab:
count -= 1
return count
a = 12
b = 18
common_divisors = count_common_divisors(a, b)
print("The number of common divisors of", a, "and", b, "is", common_divisors, ".")
C#
using System;
public class MainClass
{
public static int GCD(int a, int b)
{
if (b == 0)
{
return a;
}
return GCD(b, a % b);
}
public static int CountCommonDivisors(int a, int b)
{
int gcd_ab = GCD(a, b);
int count = 0;
for (int i = 1; i * i <= gcd_ab; i++)
{
if (gcd_ab % i == 0)
{
count += 2;
if (i * i == gcd_ab)
{
count--;
}
}
}
return count;
}
public static void Main()
{
int a = 12;
int b = 18;
int commonDivisors = CountCommonDivisors(a, b);
Console.WriteLine("The number of common divisors of {0} and {1} is {2}.", a, b, commonDivisors);
}
}
Javascript
function gcd(a, b) {
if(b === 0) {
return a;
}
return gcd(b, a % b);
}
function count_common_divisors(a, b) {
let gcd_ab = gcd(a, b);
let count = 0;
for(let i = 1; i * i <= gcd_ab; i++) {
if(gcd_ab % i === 0) {
count += 2;
if(i * i === gcd_ab) {
count--;
}
}
}
return count;
}
let a = 12;
let b = 18;
let common_divisors = count_common_divisors(a, b);
console.log(`The number of common divisors of ${a} and ${b} is ${common_divisors}.`);
Output
The number of common divisors of 12 and 18 is 4.
The time complexity of the gcd() function is O(log(min(a, b))), as it uses Euclid’s algorithm which takes logarithmic time with respect to the smaller of the two numbers.
The time complexity of the count_common_divisors() function is O(sqrt(gcd(a, b))), as it iterates up to the square root of the gcd of the two numbers.
The space complexity of both functions is O(1), as they only use a constant amount of memory regardless of the input size.
Last Updated :
13 Apr, 2023
Like Article
Save Article
Загрузить PDF
Загрузить PDF
Нахождение наибольшего общего делителя (НОД) для определенного количества чисел может быть легкой задачей, если вы умеете это делать.
-
1
Найдите делители чисел. Начните с поиска всех делителей первого и второго числа.
-
2
Сравните делители обоих чисел и найдите самое большое число, которое есть в списке делителей как первого, так и второго числа. Это число равно НОД.
Реклама
-
1
Разложите каждое число на простые множители. Простое число – это число, большее 1 и которое делится только на 1 и на само себя. Примеры простых чисел: 5, 17, 97, 331.
-
2
Найдите общие простые множители. Общий простой множитель может быть только один, или их может быть несколько.
-
3
Если у двух чисел есть только один общий простой множитель, то он равен НОД. Если у двух чисел есть несколько общих простых множителей, то их произведение равно НОД.
-
4
Изучите пример. Чтобы продемонстрировать этот метод, изучите пример, приведенный на рисунке.
Реклама
Советы
- Простое число – это число, которое делится только на 1 и на само себя.
- Знаете ли вы, что в третьем веке до н.э. математик Евклид создал алгоритм для вычисления наибольшего общего делителя двух натуральных чисел и двух многочленов?
Реклама
Об этой статье
Эту страницу просматривали 7382 раза.
Была ли эта статья полезной?
Наибольшим общим делителем (НОД) двух целых чисел называется наибольший из их общих делителей. К примеру для чисел 12 и 8, наибольшим общим делителем будет 4.
Как найти НОД?
Способов найти НОД несколько. Мы рассмотрим один из часто используемых в математике — это нахождение НОД при помощи разложения чисел на простые множители. В общем случае алгоритм будет выглядеть следующим образом:
- разложить оба числа на простые множители (подробнее о разложении чисел на простые множители смотрите тут);
- выбрать одинаковые множители, входящие в оба разложения;
- найти их произведение.
Примеры нахождения наибольшего общего делителя
Рассмотрим приведенный алгоритм на конкретных примерах:
Пример 1: найти НОД 12 и 8
1. Раскладываем 12 и 8 на простые множители:
2. Выбираем одинаковые множители, которые есть в обоих разложениях. Это: 2 и 2
3. Перемножаем эти множители и получаем: 2 · 2 = 4
Ответ: НОД (8; 12) = 2 · 2 = 4.
Пример 2: найти НОД 75 и 150
Этот пример, как и предыдущий с легкостью можно высчитать в уме и вывести ответ 75, но для лучшего понимания работы алгоритма, проделаем все шаги:
1. Раскладываем 75 и 150 на простые множители:
2. Выбираем одинаковые множители, которые есть в обоих разложениях. Это: 3, 5 и 5
3. Перемножаем эти множители и получаем: 3 · 5 · 5 = 75
Ответ: НОД (75; 150) = 3 · 5 · 5 = 75.
Частный случай или взаимно простые числа
Нередко встречаются ситуации, когда оба числа взаимно простые, т.е. общий делитель равен единице. В этом случае, алгоритм будет выглядеть следующим образом:
Пример 3: найти НОД 9 и 5
1. Раскладываем 5 и 9 на простые множители:
Видим, что одинаковых множителей нет, а значит, что это частный случай (взаимно простые числа). Общий делитель — единица.
Как найти НОД
- Нахождение путём разложения на множители
- Алгоритм Евклида
Рассмотрим два способа нахождения наибольшего общего делителя.
Нахождение путём разложения на множители
Первый способ заключается в нахождении наибольшего общего делителя путём разложения данных чисел на простые множители.
Чтобы найти НОД нескольких чисел, достаточно, разложить их на простые множители и перемножить между собой те из них, которые являются общими для всех данных чисел.
Пример 1. Найти НОД (84, 90).
Решение: Раскладываем числа 84 и 90 на простые множители:
Итак, мы подчеркнули все общие простые множители, осталось перемножить их между собой:
2 · 3 = 6.
Таким образом, НОД (84, 90) = 6.
Пример 2. Найти НОД (15, 28).
Решение: Раскладываем 15 и 28 на простые множители:
Числа 15 и 28 являются взаимно простыми, так как их наибольший общий делитель — единица.
НОД (15, 28) = 1.
Алгоритм Евклида
Второй способ (иначе его называют способом Евклида) заключается в нахождении НОД путём последовательного деления.
Сначала мы рассмотрим этот способ в применении только к двум данным числам, а затем разберёмся в том, как его применять к трём и более числам.
Если большее из двух данных чисел делится на меньшее, то число, которое меньше и будет их наибольшим общим делителем.
Пример 1. Возьмём два числа 27 и 9. Так как 27 делится на 9 и 9 делится на 9, значит, 9 является общим делителем чисел 27 и 9. Этот делитель является в тоже время и наибольшим, потому что 9 не может делиться ни на какое число, большее 9. Следовательно:
НОД (27, 9) = 9.
В остальных случаях, чтобы найти наибольший общий делитель двух чисел используется следующий порядок действий:
- Из двух данных чисел большее число делят на меньшее.
- Затем, меньшее число делят на остаток, получившийся от деления большего числа на меньшее.
- Далее, первый остаток делят на второй остаток, который получился от деления меньшего числа на первый остаток.
- Второй остаток делят на третий, который получился от деления первого остатка на второй и т. д.
- Таким образом деление продолжается до тех пор, пока в остатке не получится нуль. Последний делитель как раз и будет наибольшим общим делителем.
Пример 2. Найдём наибольший общий делитель чисел 140 и 96:
1) 140 : 96 = 1 (остаток 44)
2) 96 : 44 = 2 (остаток 8)
3) 44 : 8 = 5 (остаток 4)
4) 8 : 4 = 2
Последний делитель равен 4 — это значит:
НОД (140, 96) = 4.
Последовательное деление так же можно записывать столбиком:
Чтобы найти наибольший общий делитель трёх и более данных чисел, используем следующий порядок действий:
- Сперва находим наибольший общий делитель любых двух чисел из нескольких данных.
- Затем находим НОД найденного делителя и какого-нибудь третьего данного числа.
- Затем находим НОД последнего найденного делителя и четвёртого данного числа и так далее.
Пример 3. Найдём наибольший общий делитель чисел 140, 96 и 48. НОД чисел 140 и 96 мы уже нашли в предыдущем примере (это число 4). Осталось найти наибольший общий делитель числа 4 и третьего данного числа — 48:
48 : 4 = 12
48 делится на 4 без остатка. Таким образом:
НОД (140, 96, 48) = 4.
Онлайн калькулятор НОД и НОК двух чисел
Наибольший общий делитель (НОД)
НОД двух или более целых чисел — это наибольшее целое число, которое является делителем каждого из этих чисел.
Если натуральное число a делится на натуральное число bb, то bb называют делителем числа aa, а число aa называют кратным числа bb. aa и bb являются натуральными числами. Число gg называют общим делителем и для aa и для bb. Множество общих делителей чисел aa и bb конечно, так как ни один из этих делителей не может быть больше, чем aa. Значит, среди этих делителей есть наибольший, который называют наибольшим общим делителем чисел aa и bb и для его обозначения используют записи: НОД (a;b)(a;b) или D(a;b)(a;b)
Пример
Наибольший общий делитель (НОД) чисел 1818 и 2424 — это 66.
Как найти наибольший общий делитель (НОД)
Существует несколько способов нахождения наибольшего общего делителя (НОД) двух или более целых чисел:
- Алгоритм Евклида: НОД(a,b)=(a, b) = НОД (b,a(b, a mod b)b), где «mod» – это операция взятия остатка от деления большего числа на меньшее. Этот алгоритм можно продолжать до тех пор, пока одно из чисел не станет равно нулю. В этом случае НОД равен ненулевому числу.
Пример
НОД(18,24)=НОД(24,18)=НОД(18,6)=НОД(6,0)=6НОД(18, 24) = НОД(24, 18) = НОД(18, 6) = НОД(6, 0) = 6
- Разложение на простые множители: Найти все простые множители каждого из чисел и их степени. НОД будет равен произведению всех общих простых множителей в минимальной степени.
Пример
НОД(60,84)=22⋅31=12(60, 84) = 2^{2} cdot 3^{1} = 12, так как общие простые множители −2- 2 и 33, их минимальные степени −2- 2 и 11 соответственно.
- Таблица делителей: Составить таблицы всех делителей каждого числа и найти наибольшее общее число, которое является делителем обоих чисел. Этот метод не рекомендуется для больших чисел, так как он требует много времени и усилий.
Наименьшее общее кратное (НОК)
НОК двух или более целых чисел — это наименьшее число, которое делится на каждое из этих чисел без остатка.
Общими кратными чисел называются числа которые делятся на исходные без остатка. Например для чисел 2525 и 5050 общими кратными будут числа 50,100,150,20050,100,150,200 и т.д Наименьшее из общих кратных будет называться НОК и обозначается НОК(a;b)(a;b) или K(a;b).(a;b).
Пример
Наименьшее общее кратное чисел 88 и 1212 – это 2424. Т.е. НОК (8,12)=24(8, 12) = 24.
Как найти наименьшее общее кратное (НОК)
Чтобы найти НОК двух чисел, необходимо:
- Разложить числа на простые множители;
- Выписать множители, входящие в состав первого числа и добавить к ним множители, которые входят в состав второго и не ходят в состав первого;
- Найти произведение чисел, найденных на шаге 2. Полученное число и будет искомым наименьшим общим кратным.
Пример
Рассмотрим два числа: 88 и 1212. Найдем их НОКНОК:
- Разложим 88 и 1212 на простые множители: 8=23,12=22⋅38 = 2^3, 12 = 2^2 cdot 3.
- Выпишем все простые множители: 23⋅32^3 cdot 3.
- Для каждого простого множителя выберем наибольшую кратность: 232^3 и 33.
- Умножим выбранные простые множители между собой: 23⋅3=242^3 cdot 3 = 24.
Таким образом, НОК чисел 88 и 1212 равен 2424.
Свойства НОД и НОК
- Любое общее кратное чисел aa и bb делится на K(a;b)(a;b);
- Если a⋮bavdots b , то К(a;b)=a(a;b)=a;
- Если К(a;b)=k(a;b)=k и mm-натуральное число, то К(am;bm)=km(am;bm)=km. Если dd-общий делитель для aa и bb,то К(ad;bdfrac{a}{d};frac{b}{d})= kd frac{k}{d}
- Если a⋮cavdots c и b⋮cbvdots c ,то abcfrac{ab}{c} – общее кратное чисел aa и bb;
- Для любых натуральных чисел aa и bb выполняется равенство D(a;b)⋅К(a;b)=abD(a;b)cdot К(a;b)=ab;
- Любой общий делитель чисел aa и bb является делителем числа D(a;b)D(a;b).
