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
В данной статье мы поговорим о том, как найти все делители числа. Начнем с доказательства теоремы, с помощью которой можно задать вид всех делителей определенного числа. Далее возьмем примеры нахождения всех нужных делителей и покажем, как именно определить, сколько делителей имеет конкретное число. В последнем пункте подробно рассмотрим примеры задач на нахождение общих делителей нескольких чисел.
Как найти все делители числа
Чтобы понять материал, изложенный в данном пункте, нужно хорошо знать, что вообще из себя представляют кратные числа и делители. Здесь мы поговорим только о поиске делителей натуральных чисел, т.е. целых положительных. Этим можно ограничиться, поскольку свойство делимости гласит, что делители целого отрицательного числа аналогичны делителям целого положительного, которое будет противоположным по отношению к этому числу. Также сразу уточним, что у нуля есть бесконечно большое число делителей, и находить их смысла не имеет, поскольку в итоге все равно получится 0.
Если речь идет о простом числе, то его можно разделить только на единицу и на само себя. Значит, у любого простого числа a есть всего 4 делителя, два из которых больше 0 и два меньше: 1, -1, a, -a. Возьмем простое число 7: у него есть делители 7, -7, 1 и -1, и все. Еще один пример: 367 – тоже простое число, которое можно разделить лишь на 1, -1, 367 и -367.
Сложнее определить все делители составного числа. Сформулируем теорему, которая лежит в основе данного действия.
Допустим, у нас есть выражение, означающее каноническое разложение числа на простые множители, вида a=p1s1·p2s2·…·pnsn. Тогда натуральными делителями числа a будут следующие числа: d=p1t2·p2t2·…·pntn, где t1=0, 1, …, s1, t2=0, 1, …, s2, …, tn=0, 1, …, sn.
Перейдем к доказательству этой теоремы. Зная основное определение делимости, мы можем утверждать, что a можно разделить на d, если есть такое число q, что делает верным равенство a=d·q, т.е. q=p1(s1−t1)·p2(s2-t2)·…·pn(sn-tn).
Любое число, делящее a, будет иметь именно такой вид, поскольку, согласно свойствам делимости, других простых множителей, кроме p1, p2, …, pn, оно иметь не может, а их показатели в данном случае не превысят s1, s2, …, sn.
Учитывая доказательство этой теоремы, мы можем сформировать схему нахождения всех положительных делителей данного числа.
Для этого нужно выполнить следующие действия:
- Выполнить каноническое разложение на простые множители и получить выражение вида a=p1s1·p2s2·…·pnsn.
- Найти все значения d=p1t2·p2t2·…·pntn, где числа t1, t2, …, tn будут принимать независимо друг от друга каждое из значений t1=0, 1, …, s1, t2=0, 1, …, s2, …, tn=0, 1, …, sn.
Самым трудным в таком расчете является именно перебор всех комбинаций указанных значений. Разберем подробно решения нескольких задач, чтобы наглядно показать применение данной схемы на практике.
Условие: найти все делители 8.
Решение
Разложим восьмерку на простые множители и получим 8=2·2·2. Переведем разложение в каноническую форму и получим 8=23. Следовательно, a=8, p1=2, s1=3.
Поскольку все делители восьмерки будут значениями p1t1=2t1, то t1 может принять значения нуля, единицы, двойки, тройки. 3 будет последним значением, ведь s1=3. Таким образом, если t1=0, то 2t1=20=1, если 1, то 2t1=21=2, если 2, то 2t1=22=4, а если 3, то 2t1=23=8.
Для нахождения делителей удобно все полученные значения оформлять в виде таблицы:
t1 | 2t1 |
0 | 20=1 |
1 | 21=2 |
2 | 22=4 |
3 | 23=8 |
Значит, положительными делителями восьмерки будут числа 1, 2, 4 и 8, а отрицательными −1, −2, −4 и −8.
Ответ: делителями данного числа будут ±1, ±2, ±4, ±8.
Возьмем пример чуть сложнее: в нем при разложении числа получится не один, а два множителя.
Условие: найдите все делители числа 567, являющиеся натуральными числами.
Решение
Начнем с разложения данного числа на простые множители.
56718963217133337
Приведем разложение к каноническому виду и получим 567=34·7. Затем перейдем к вычислению всех натуральных множителей. Для этого будем присваивать t1 и t2 значения 0, 1, 2, 3, 4 и 0, 1, вычисляя при этом значения 3t1·7t2. Результаты будем вносить в таблицу:
t1 | t2 | 3t1·7t2 |
0 | 0 | 30·70=1 |
0 | 1 | 30·71=7 |
1 | 0 | 31·70=3 |
1 | 1 | 31·71=21 |
2 | 0 | 32·70=9 |
2 | 1 | 32·71=63 |
3 | 0 | 33·70=27 |
3 | 1 | 33·71=189 |
4 | 0 | 34·70=81 |
4 | 1 | 34·71=567 |
Ответ: натуральными делителями 567 будут числа 27, 63, 81, 189, 1, 3, 7, 9, 21 и 567.
Продолжим усложнять наши примеры – возьмем четырехзначное число.
Условие: найти все делители 3 900, которые будут больше 0.
Решение
Проводим разложение данного числа на простые множители. В каноническом виде оно будет выглядеть как 3 900=22·3·52·13. Теперь приступаем к нахождению положительных делителей, подставляя в выражение 2t1·3t2·5t3·13t4 значения t1, равные 0, 1 и 2, t2=0,1, t3=0, 1, 2, t4=0, 1. Результаты представляем в табличном виде:
t1 | t2 | t3 | t4 | 2t1·3t2·5t3·13t4 |
0 | 0 | 0 | 0 | 20·30·50·130=1 |
0 | 0 | 0 | 1 | 20·30·50·131=13 |
0 | 0 | 1 | 0 | 20·30·51·130=5 |
0 | 0 | 1 | 1 | 20·30·51·131=65 |
0 | 0 | 2 | 0 | 20·30·52·130=25 |
0 | 0 | 2 | 1 | 20·30·52·131=325 |
0 | 1 | 0 | 0 | 20·31·50·130=3 |
0 | 1 | 0 | 1 | 20·31·50·131=39 |
0 | 1 | 1 | 0 | 20·31·51·130=15 |
0 | 1 | 1 | 1 | 20·31·51·131=195 |
0 | 1 | 2 | 0 | 20·31·52·130=75 |
0 | 1 | 2 | 1 | 20·31·52·131=975 |
t1 | t2 | t3 | t4 | 2t1·3t2·5t3·13t4 |
1 | 0 | 0 | 0 | 21·30·50·130=2 |
1 | 0 | 0 | 1 | 21·30·50·131=26 |
1 | 0 | 1 | 0 | 21·30·51·130=10 |
1 | 0 | 1 | 1 | 21·30·51·131=130 |
1 | 0 | 2 | 0 | 21·30·52·130=50 |
1 | 0 | 2 | 1 | 21·30·52·131=650 |
1 | 1 | 0 | 0 | 21·31·50·130=6 |
1 | 1 | 0 | 1 | 21·31·50·131=78 |
1 | 1 | 1 | 0 | 21·31·51·130=30 |
1 | 1 | 1 | 1 | 21·31·51·131=390 |
1 | 1 | 2 | 0 | 21·31·52·130=150 |
1 | 1 | 2 | 1 | 21·31·52·131=1950 |
t1 | t2 | t3 | t4 | 2t1·3t2·5t3·13t4 |
2 | 0 | 0 | 0 | 22·30·50·130=4 |
2 | 0 | 0 | 1 | 22·30·50·131=52 |
2 | 0 | 1 | 0 | 22·30·51·130=20 |
2 | 0 | 1 | 1 | 22·30·51·131=260 |
2 | 0 | 2 | 0 | 22·30·52·130=100 |
2 | 1 | 0 | 1 | 22·30·52·131=1300 |
2 | 1 | 0 | 0 | 22·31·50·130=12 |
2 | 1 | 0 | 1 | 22·31·50·131=156 |
2 | 1 | 1 | 0 | 22·31·51·130=60 |
2 | 1 | 1 | 1 | 22·31·51·131=780 |
2 | 1 | 2 | 0 | 22·31·52·130=300 |
2 | 1 | 2 | 1 | 22·31·52·131=3900 |
Ответ: делителями числа 3 900 будут:195, 260, 300, 325, 390, 650, 780, 975, 75, 78, 100, 130, 150, 156, 13,15, 20, 25, 26, 30, 39, 50,52, 60, 65, 1, 2, 3, 4, 5, 6, 10, 12, 1 300, 1 950, 3 900
Как определить количество делителей конкретного числа
Чтобы узнать, сколько положительных делителей у конкретного числа a, каноническое разложение которого выглядит как a=p1s1·p2s2·…·pnsn, нужно найти значение выражения (s1+1) ·(s2+1) ·…·(sn+1). О количестве наборов переменных t1, t2, …, tn мы можем судить по величине записанного выражения.
Покажем на примере, как это вычисляется. Определим, сколько будет натуральных делителей у числа 3 900, которое мы использовали в предыдущей задаче. Каноническое разложение мы уже записывали: 3 900=22·3·52·13. Значит, s1=2, s2=1, s3=2, s4=1. Теперь подставим значения s1, s2, s3 и s4 в выражение (s1+1) ·(s2+1) ·(s3+1) ·(s4+1) и вычислим его значение. Имеем (2+1)·(1+1)·(2+1)·(1+1)=3·2·3·2=36. Значит, это число имеет всего 36 делителей, являющихся натуральными числами. Пересчитаем то количество, что у нас получилось в предыдущей задаче, и убедимся в правильности решения. Если учесть и отрицательные делители, которых столько же, сколько и положительных, то получится, что у данного числа всего будет 72 делителя.
Условие: определите, сколько делителей имеет 84.
Решение
Раскладываем число на множители.
844221712237
Записываем каноническое разложение: 84=22·3·7. Определяем, сколько у нас получится положительных делителей: (2+1)·(1+1)·(1+1) =12. Для учета отрицательных нужно умножить это число на 2:2·12=24.
Ответ: всего у 84 будет 24 делителя – 12 положительных и 12 отрицательных.
Как вычислить общие делители нескольких чисел
Зная свойства наибольшего общего делителя, можно утверждать, что количество делителей некоторого набора целых чисел будет совпадать с количеством делителей НОД тех же чисел. Это будет справедливо не только для двух чисел, но и для большего их количества. Следовательно, чтобы вычислить все общие делители нескольких чисел, надо определить их наибольший общий множитель и найти все его делители.
Разберем пару таких задач.
Условие: сколько будет натуральных общих делителей у чисел 140 и 50? Вычислите их все.
Решение
Начнем с вычисления НОД (140, 50).
Для этого нам потребуется алгоритм Евклида:
140=50·2+40, 50=40·1+10, 40=10·4, значит, НОД (50, 140)=10.
Далее выясним, сколько положительных делителей есть у десяти. Разложим его на простые множители и получим 20·50=1, 20·51=5, 21·50=2 и 21·51=10. Значит, все натуральные общие делители исходного числа – это 1, 2, 5 и 10, а всего их четыре.
Ответ: данные числа имеют четыре натуральных делителя, равные 10, 5, 2 и 1.
Условие: выясните, сколько общих положительных делителей есть у чисел 585, 315, 90 и 45.
Решение
Вычислим их наибольший общий делитель, разложив число на простые множители. Поскольку 90=2·3·3·5, 45=3·3·5, 315=3·3·5·7 и 585=3·3·5·13, то таким делителем будет 5: НОД (90, 45, 315, 585) =3·3·5=32·5.
Чтобы узнать количество этих чисел, нужно выяснить, сколько положительных делителей имеет НОД.
Считаем:
НОД (90, 45, 315, 585) =32·5:(2+1)·(1+1) =6.
Ответ: у данных чисел шесть общих делителей.
Загрузить PDF
Загрузить PDF
Нахождение наибольшего общего делителя (НОД) для определенного количества чисел может быть легкой задачей, если вы умеете это делать.
-
1
Найдите делители чисел. Начните с поиска всех делителей первого и второго числа.
-
2
Сравните делители обоих чисел и найдите самое большое число, которое есть в списке делителей как первого, так и второго числа. Это число равно НОД.
Реклама
-
1
Разложите каждое число на простые множители. Простое число – это число, большее 1 и которое делится только на 1 и на само себя. Примеры простых чисел: 5, 17, 97, 331.
-
2
Найдите общие простые множители. Общий простой множитель может быть только один, или их может быть несколько.
-
3
Если у двух чисел есть только один общий простой множитель, то он равен НОД. Если у двух чисел есть несколько общих простых множителей, то их произведение равно НОД.
-
4
Изучите пример. Чтобы продемонстрировать этот метод, изучите пример, приведенный на рисунке.
Реклама
Советы
- Простое число – это число, которое делится только на 1 и на само себя.
- Знаете ли вы, что в третьем веке до н.э. математик Евклид создал алгоритм для вычисления наибольшего общего делителя двух натуральных чисел и двух многочленов?
Реклама
Об этой статье
Эту страницу просматривали 7358 раз.
Была ли эта статья полезной?
Наибольшим общим делителем (НОД) двух целых чисел называется наибольший из их общих делителей. К примеру для чисел 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.