Рубрики

Сумма общих делителей двух чисел A и B

Конкурентное программирование, Математика

Учитывая два числа A и B, задача состоит в том, чтобы найти сумму общих множителей двух чисел A и B. Числа A и B меньше 10 ^ 8.


Примеры:

Input: A = 10, B = 15
Output: Sum = 6
The common factors are 1, 5, so their sum is 6 

Input: A = 100, B = 150
Output: Sum = 93

Наивный подход: итерируйте от i = 1 до минимума A и B и проверьте, является ли i фактором как A, так и B. Если i является фактором A и B, то прибавьте его к сумме. Показать сумму в конце цикла.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация вышеуказанного подхода
#include <bits/stdc++.h>

using namespace std;

  
// выводим сумму общих факторов

int sum(int a, int b)

{

    // сумма общих факторов

    int sum = 0;

  

    // итерация от 1 до минимума a и b

    for (int i = 1; i <= min(a, b); i++)

  

        // если я общий фактор

        // обоих чисел

        if (a % i == 0 && b % i == 0)

            sum += i;

  

    return sum;

}

  
// Код драйвера

int main()

{

    int A = 10, B = 15;

  

    // выводим сумму общих факторов

    cout << "Sum = " << sum(A, B) << endl;

  

    return 0;

}

Джава

// Java реализация вышеупомянутого подхода

import java.io.*;

  

class GFG {

      

  

  
// выводим сумму общих факторов

static int sum(int a, int b)

{

    // сумма общих факторов

    int sum = 0;

  

    // итерация от 1 до минимума a и b

    for (int i = 1; i <= Math.min(a, b); i++)

  

        // если я общий фактор

        // обоих чисел

        if (a % i == 0 && b % i == 0)

            sum += i;

  

    return sum;

}

  
// Код драйвера

  

  

    public static void main (String[] args) {

            int A = 10, B = 15;

  

    // выводим сумму общих факторов

    System.out.print("Sum = " + sum(A, B));

    }

}
// Этот код предоставлен shs ..

Python 3

# Python 3 реализация
# выше подход

  
# выведите сумму общих факторов

def sum(a, b):

  

    # сумма общих факторов

    sum = 0

  

    # итерация от 1 до минимума a и b

    for i in range (1, min(a, b)):

  

        # если я общий фактор

        № обоих чисел

        if (a % i == 0 and b % i == 0):

            sum += i

  

    return sum

  
Код водителя

A = 10

B = 15

  
# выведите сумму общих факторов

print("Sum =", sum(A, B))

  
# Этот код добавлен
# от Akanksha Rai

C #

// C # реализация вышеуказанного подхода

  

  

using System;

  

class GFG {

      

  

  
// выводим сумму общих факторов

static int sum(int a, int b)

{

    // сумма общих факторов

    int sum = 0;

  

    // итерация от 1 до минимума a и b

    for (int i = 1; i <= Math.Min(a, b); i++)

  

        // если я общий фактор

        // обоих чисел

        if (a % i == 0 && b % i == 0)

            sum += i;

  

    return sum;

}

  
// Код драйвера

  

  

    public static void Main () {

            int A = 10, B = 15;

  

    // выводим сумму общих факторов

    Console.WriteLine("Sum = " + sum(A, B));

    }

}
// Этот код предоставлен shs ..

PHP

<?php
// PHP реализация вышеупомянутого подхода

  
// выводим сумму общих факторов

function sum($a, $b)

{

    // сумма общих факторов

    $sum = 0;

  

    // итерация от 1 до минимума a и b

    for ($i = 1; $i <= min($a, $b); $i++)

  

        // если я общий фактор

        // обоих чисел

        if ($a %$i == 0 && $b %$i == 0)

            $sum += $i;

  

    return $sum;

}

  
// Код драйвера

$A = 10; $B = 15;

  
// выводим сумму общих факторов

echo "Sum = " , sum($A, $B);

  
// Этот код предоставлен shs.
?>

Выход:

Sum = 6

Эффективный подход заключается в использовании той же концепции, что и в общих делителях двух чисел . Вычислите наибольший общий делитель (gcd) из заданных двух чисел, а затем найдите сумму делителей этого gcd.

C ++

// C ++ реализация вышеуказанного подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для вычисления gcd двух чисел

int gcd(int a, int b)

{

    if (a == 0)

        return b;

    return gcd(b % a, a);

}

  
// Функция для вычисления всех общих делителей
// из двух заданных чисел
// a, b -> введите целые числа

int sumcommDiv(int a, int b)

{

    // найти gcd a, b

    int n = gcd(a, b);

  

    // Находим сумму делителей n.

    int sum = 0;

    for (int i = 1; i <= sqrt(n); i++) {

  

        // если 'i' является фактором n

        if (n % i == 0) {

  

            // проверяем равны ли делители

            if (n / i == i)

                sum += i;

            else

                sum += (n / i) + i;

        }

    }

  

    return sum;

}

  
// Драйвер программы для запуска дела

int main()

{

    int a = 10, b = 15;

    cout << "Sum = " << sumcommDiv(a, b);

  

    return 0;

}

Джава

// Java реализация вышеуказанного подхода

  

import java.io.*;

  

class GFG {

      
// Функция для вычисления gcd двух чисел

static int gcd(int a, int b) 

{ 

    if (a == 0) 

        return b; 

    return gcd(b % a, a); 

} 

  
// Функция для вычисления всех общих делителей
// из двух заданных чисел
// a, b -> введите целые числа

static int sumcommDiv(int a, int b) 

{ 

    // найти gcd a, b

    int n = gcd(a, b); 

  

    // Находим сумму делителей n.

    int sum = 0; 

    for (int i = 1; i <= Math.sqrt(n); i++) { 

  

        // если 'i' является фактором n

        if (n % i == 0) { 

  

            // проверяем равны ли делители

            if (n / i == i) 

                sum += i; 

            else

                sum += (n / i) + i; 

        } 

    } 

  

    return sum; 

} 

  
// Драйвер программы для запуска дела

    public static void main (String[] args) {

      

    int a = 10, b = 15; 

    System.out.println("Sum = " + sumcommDiv(a, b)); 

    }

}

python3

# Python 3 реализация вышеуказанного подхода

from math import gcd,sqrt

  
# Функция для вычисления всех общих делителей
№ двух заданных чисел
# a, b -> введите целые числа

def sumcommDiv(a, b):

    # найти gcd a, b

    n = gcd(a, b)

  

    # Найти сумму делителей n.

    sum = 0

    N = int(sqrt(n))+1

    for i in range(1,N,1):

        # если 'i' является фактором n

        if (n % i == 0):

            # проверить, равны ли делители

            if (n / i == i):

                sum += i

            else:

                sum += (n / i) + i

          

    return sum

  
# Драйвер программы для запуска дела

if __name__ == '__main__':

    a = 10

    b = 15

    print("Sum =",int(sumcommDiv(a, b)))

  
# Этот код предоставлен
# Surendra_Gangwar

C #

// C # реализация вышеуказанного подхода

  

using System;

  

public class GFG{

          
// Функция для вычисления gcd двух чисел

static int gcd(int a, int b) 

{ 

    if (a == 0) 

        return b; 

    return gcd(b % a, a); 

} 

  
// Функция для вычисления всех общих делителей
// из двух заданных чисел
// a, b -> введите целые числа

static int sumcommDiv(int a, int b) 

{ 

    // найти gcd a, b

    int n = gcd(a, b); 

  

    // Находим сумму делителей n.

    int sum = 0; 

    for (int i = 1; i <= Math.Sqrt(n); i++) { 

  

        // если 'i' является фактором n

        if (n % i == 0) { 

  

            // проверяем равны ли делители

            if (n / i == i) 

                sum += i; 

            else

                sum += (n / i) + i; 

        } 

    } 

  

    return sum; 

} 

  
// Драйвер программы для запуска дела

    static public void Main (){

        int a = 10, b = 15; 

        Console.WriteLine("Sum = " + sumcommDiv(a, b));

    }

}

PHP

<?php
// PHP реализация вышеупомянутого подхода

  
// Функция для вычисления gcd двух чисел

function gcd($a, $b)

{

    if ($a == 0)

        return $b;

    return gcd($b % $a, $a);

}

  
// Функция для вычисления всех общих делителей
// из двух заданных чисел
// a, b -> введите целые числа

function  sumcommDiv($a, $b)

{

    // найти gcd a, b

$n = gcd($a, $b);

  

    // Находим сумму делителей n.

    $sum = 0;

    for ($i = 1; $i <= sqrt($n); $i++) {

  

        // если 'i' является фактором n

        if ($n % $i == 0) {

  

            // проверяем равны ли делители

            if ($n / $i == $i)

                $sum += $i;

            else

                $sum += ($n / $i) + $i;

        }

    }

  

    return $sum;

}

  
// Драйвер программы для запуска дела

    $a = 10;

    $b = 15;

    echo "Sum = " , sumcommDiv($a, $b);

  

  
?>

Выход:

Sum = 6

Рекомендуемые посты:

Сумма общих делителей двух чисел A и B

0.00 (0%) 0 votes