A10. Делители числа.
Задание. Найдите сумму всех общих
натуральных делителей чисел 42, 56, 84.
Варианты ответов.
- 23;
- 9;
- 24;
- 26;
- 10.
Теория. здесь
Анализ. Не путать с понятием «наибольший общий делитель». Общим
делителем называется число, на которое делятся все числа, а наибольший общий
делитель – наибольшее из таких чисел, на которые делятся все числа.
Так же не путать с разложением на линейные множители.
Решение. Здесь мы будем раскладывать на простые множители, а затем
искать общие. Раскладываем числа на простые множители
Общие
делители: 2, 7, 14 и не забываем, что 1 является делителем любого числа,
поэтому он тоже общий!
Ответ. 3
Найди верный ответ на вопрос ✅ «Как найти сумму всех общих делителей чисел 36 и 54. Объясните как нашли сумму …» по предмету 📙 Математика, а если ответа нет или никто не дал верного ответа, то воспользуйся поиском и попробуй найти ответ среди похожих вопросов.
Искать другие ответы
Главная » Математика » Как найти сумму всех общих делителей чисел 36 и 54. Объясните как нашли сумму
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
Как найти сумму всех общих делителей чисел 36 и 54.
Объясните как нашли сумму.
Перед вами страница с вопросом Как найти сумму всех общих делителей чисел 36 и 54?, который относится к
категории Математика. Уровень сложности соответствует учебной программе для
учащихся 5 – 9 классов. Здесь вы найдете не только правильный ответ, но и
сможете ознакомиться с вариантами пользователей, а также обсудить тему и
выбрать подходящую версию. Если среди найденных ответов не окажется
варианта, полностью раскрывающего тему, воспользуйтесь «умным поиском»,
который откроет все похожие ответы, или создайте собственный вопрос, нажав
кнопку в верхней части страницы.
Опубликовано 30.09.2017 по предмету Математика от Гость
Ответ оставил Гость
36 и 54 делятся на 6;1;2;3;9;18 отсюда следует 6+1+2+3+9+18=39
Оцени ответ
Загрузить картинку
Новые вопросы
Математика, опубликовано 04.08.2021
официальный курс обмена 1 евро по отношению к российскому рублю, установленный ЦБ РФ на 31.12.2016 (формат 00.0000)
Математика, опубликовано 28.04.2021
(29780-33)*24:197+22546=?
помогите пш((
Математика, опубликовано 17.09.2020
какое число надо вписать в окошко чтобы равенство стало верным _-220=883-302
Не нашёл ответ?
Если тебя не устраивает ответ или его нет, то попробуй воспользоваться поиском на сайте и найти похожие ответы по предмету Математика.
Найти другие ответы
