Максимальная сумма различных чисел, для которых НОК этих чисел равна N

Опубликовано: 19 Января, 2022

Дано положительное число N. Задача состоит в том, чтобы найти максимальную сумму различных чисел, такую, что НОК всех этих чисел равняется N.
Примеры:

 Ввод: 2
Выход: 3
Вы можете иметь различные числа: 
всего 1 и 2, а их сумма равна 3.

Ввод: 5
Выход: 6

Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.

As the LCM of all the numbers is N. So all the numbers must be the divisors of N and all the numbers are distinct so answer must be the sum of all the divisors of N. To find all the divisors efficiently refer to article https://www.geeksforgeeks.org/find-all-divisors-of-a-natural-number-set-2/

C++

// C++ program to find the max sum of
// numbers whose lcm is n
#include<bits/stdc++.h>
using namespace std;
 
// Returns maximum sum of numbers with
// LCM as N
int maxSumLCM(int n)
{
    int max_sum = 0;  // Initialize result
 
    // Finding a divisor of n and adding
    // it to max_sum
    for (int i=1; i*i<=n; i++)
    {
        if (n%i == 0)
        {
            max_sum += i;
            if (n/i != i)
                max_sum += (n/i);
        }
    }
 
    return max_sum;
}
 
// Driver code
int main()
{
    int n = 2;
    cout << MaxSumLCM(n) << endl;
    return 0;
}

Java

// Java program to find the max sum of
// numbers whose lcm is n
 
class MaxSum
{
    // Returns maximum sum of numbers with
    // LCM as N
    static int maxSumLCM(int n)
    {
        int max_sum = 0;  // Initialize result
      
        // Finding a divisor of n and adding
        // it to max_sum
        for (int i=1; i*i<=n; i++)
        {
            if (n%i == 0)
            {
                max_sum += i;
                if (n/i != i)
                    max_sum += (n/i);
            }
        }
         
        return max_sum;
    }
     
    // main function
    public static void main (String[] args)
    {
        int n = 2;
        System.out.println(maxSumLCM(n));
    }
}

Python3

# Python3 program to find the max sum of
# numbers whose lcm is n
 
# Returns maximum sum of numbers with
# LCM as N
def maxSumLCM(n) :
     
    # Initialize result
    max_sum = 0
 
    # Finding a divisor of n and adding
    # it to max_sum
    i = 1
    while(i * i<= n ):
        if (n % i == 0) :
            max_sum = max_sum + i
            if (n // i != i) :
                max_sum = max_sum + (n // i)
        i = i + 1
     
    return max_sum
 
# Driver code
n = 2
print(maxSumLCM(n))
 
# This code is contributed by Nikita Tiwari.

C#

// C# program to find the max sum
// of numbers whose lcm is n
using System;
 
class MaxSum
{
     
    // Returns maximum sum of 
    // numbers with LCM as N
    static int maxSumLCM(int n)
    {
         
         // Initialize result
         int max_sum = 0;
     
        // Finding a divisor of n and
        // adding it to max_sum
        for (int i = 1; i * i <= n; i++)
        {
            if (n % i == 0)
            {
                max_sum += i;
                if (n / i != i)
                    max_sum += (n / i);
            }
        }
         
        return max_sum;
    }
     
    // Driver Code
    public static void Main (String[] args)
    {
        int n = 2;
        Console.Write(maxSumLCM(n));
    }
}
 
// This code is contributed by parashar..

PHP

<?php
// PHP program to find
// the max sum of numbers
// whose lcm is n
 
// Returns maximum sum
// of numbers with
// LCM as N
function maxSumLCM($n)
{
    // Initialize result
    $max_sum = 0;
 
    // Finding a divisor
    // of n and adding
    // it to max_sum
    for ($i = 1;
         $i * $i <= $n; $i++)
    {
        if ($n % $i == 0)
        {
            $max_sum += $i;
            if ($n / $i != $i)
                $max_sum += ($n / $i);
        }
    }
 
    return $max_sum;
}
 
// Driver code
$n = 2;
echo MaxSumLCM($n);
     
// This code is contributed
// by ajit
?>

Javascript

<script>
 
// Javascript program to find the max sum of
// numbers whose lcm is n
 
// Returns maximum sum of numbers with
// LCM as N
function maxSumLCM(n)
{
    let max_sum = 0; // Initialize result
 
    // Finding a divisor of n and adding
    // it to max_sum
    for (let i=1; i*i<=n; i++)
    {
        if (n%i == 0)
        {
            max_sum += i;
            if (n/i != i)
                max_sum += (n/i);
        }
    }
 
    return max_sum;
}
 
// Driver code
  
    let n = 2;
    document.write(maxSumLCM(n) + "<br>");
     
// This code is contributed by Mayank Tyagi
 
</script>

Выход:

Эта статья предоставлена Ayush Jha . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Misc Школьное программирование

Максимальная сумма различных чисел, для которых НОК этих чисел равна N

C++

Java

Python3

C#

PHP

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ