Как найти максимальную сумму делителей на питоне - Сайт, где вы сможете решить свои вопросы

Дано число n. Найдите число из диапазона от 1 до n с максимальной суммой своих делителей (включая непростые делители, 1 и само число). Если таких чисел несколько, выведите минимальное из них.

Входные данные
На вход программе подается натуральное n≤104.

Выходные данные
Выведите искомое число.
у меня получилось так:

Python

n = int(input())
max1 = [1]
sum1 = 0
for j in range(1, n+1):
    for i in range(1, j+1):
        if j%i == 0:
            sum1 += i
    if sum1 > max1[0]:
        max1[0] = j
        sum1 = 0
    elif max1[0] == sum1:
        max1.append(j)
        sum1 = 0
if len(max1)>1:
    for g in max1:
        min1 = 123445666789
        if g<min1:
            min1=g
    print(min1)
else:
    print(max1[0])

Однако программа делает совсем не то, что нужно. Где ошибки?

Источник

Ученик

(201),
на голосовании

2 года назад

Голосование за лучший ответ

Роман Щербаков

Знаток

(450)

2 года назад

a,b = map(int,input().split())
max1 = 0
max2 = 0
for i in range(a,b+1):
for j in range(1,i//2+1):
if i % j == 0:
max1 += j
if max1 > max2 :
max2 = max1
d = j
pritn(d,max2)

Роман ЩербаковЗнаток (450)

2 года назад

a,b = map(int,input().split())
max1 = 0
max2 = 0
for i in range(a,b+1):
for j in range(1,i//2+1):
if i % j == 0:
max1 += j
if max1 > max2 :
max2 = max1
d = j
print(d,max2)

Роман ЩербаковЗнаток (450)

2 года назад

a,b = map(int,input().split())# ввод
max1 = 0
max2 = 0# cчётчики
for i in range(a,b+1):# перебор чисел от а до б
for j in range(1,i//2+1):# смотрим все делители числа
if i % j == 0:
max1 += j
if max1 >= max2 :# поиск того что надо
max2 = max1
d = i
max1 = 0
max2 += d# к последнему прибавляем число так как любое число является делителем самого себя и наш перебор его не включит
print(d,max2)

asdsgfdg gfdsdsgrУченик (181)

2 года назад

a = int(input())
b = int(input())
max1 = 0
max2 = 0
for i in range(a,b+1):
for j in range(1,i+1):
if i % j == 0:
max1 += j
if max1 >= max2:
max2 = max1
x = i
max1 = 0

print(x,max2)

Источник

Делитель — это число, на которое нацело делится делимое. У делимого может быть один или несколько делителей, найти их все можно с помощью простого алгоритма, который без проблем реализуется на Python 3.

Нахождение делителей числа

С практической точки зрения будет полезно, если программа на Python не только будет находить делители числа, искать их сумму, определять минимальный и максимальный, а также простые делители.

Каждая подзадача так или иначе связана с предыдущей, поэтому код последующей программы — это немного модернизированный код предыдущей. Кроме того, весь функционал при необходимости можно объединить в одной программе.

Алгоритм нахождения очень простой. В цикле перебираются значения от делимого минус единица до двух включительно. Если делимое нацело делится на текущее значение, то оно является делителем.

Пользователь вводит целое число, делителей которого будет искать программа, тогда код выглядит так:

numb = int(input("Введите целое число: "))
print("Результат:", end = " ")
for i in range(numb - 1, 1, -1):
    if (numb % i == 0):
        print(i, end = " ")

Например, пользователь ввёл число 625. Программа начинает цикл со значения 624, в цикле проверяется, делится ли нацело 625 на 624, затем цикл переходит на следующую итерацию и работает уже с числом 623 и так до двух. Таким образом, вывод программы будет следующим:

Введите целое число: 625
Результат: 125 25 5

Простые делители числа

Простой делитель — это делитель, который делится только на единицу и самого себя. Для нахождения простых делителей с помощью Python нужно немного модернизировать программу, добавив в неё дополнительный цикл for и переменную счётчик.

Программа построена по следующему алгоритму:

Обнулить счётчик.
В цикле искать делители.
Если найден, искать во вложенном цикле его делители. Это для того, чтобы определить: является ли он простым.
Если найден, увеличить счётчик.
Если счётчик равен нулю, то число простое и надо вывести значение делителя в консоль.
Перейти на следующую итерацию внешнего цикла.

Цикл теперь выглядит так:

numb = int(input("Введите целое число: "))
print("Простые:", end = " ")
for i in range(numb - 1, 1, -1):
    is_simple = 0 # Счётчик
    if (numb % i == 0):
        for j in range(i - 1, 1, -1):
            if (i % j == 0):
                is_simple = is_simple + 1 # Увеличиваем, если находим делитель
        if (is_simple == 0): # Если делителей не было найдено, выводим
            print(i, end = " ")

Понятно, что если значение счётчика больше нуля — то число точно не простое. Можно оптимизировать немного код и сразу завершать вложенный цикл после увеличения счётчика. Для этого можно воспользоваться оператором break в условном операторе, находящемся во вложенном цикле.

Результат работы программы:

Введите целое число: 63
Простые: 7 3

Делители расположены в порядке убывания. И если надо вывести только самый большой простой делитель с помощью Python, то можно после того, как выведется первое число, воспользоваться оператором break для выхода из цикла.

Сумма делителей

Для того чтобы найти сумму всех делителей числа с помощью Python, достаточно добавить в начальную программу переменную, к которой в цикле будет прибавляться каждый найденный делитель.

Код программы:

numb = int(input("Введите целое число: "))
sum_of_dividers = 0
for i in range(numb - 1, 1, -1):
    if (numb % i == 0):
        sum_of_dividers += i
print("Сумма:", sum_of_dividers)

Результат выполнения кода:

Введите целое число: 63
Сумма: 40

Количество делителей

Этот вариант программы также лишь незначительно отличается от изначального. Для подсчёта делителей нужно ввести переменную-счётчик, к которой будет прибавляться единица каждый раз, когда условие «numb % i == 0» будет выполняться.

numb = int(input("Введите целое число: "))
count_of_dividers = 0
for i in range(numb - 1, 1, -1):
    if (numb % i == 0):
        count_of_dividers += 1
print("Количество равно:", count_of_dividers)

Результаты выполнения программы:

Введите целое число: 63
Количество равно: 4

Максимальный и минимальный делитель

Для нахождения минимального и максимального делителя в код на Python нужно добавить две переменные: min_divider и max_divider. В цикле делитель будет сравниваться со значением этих переменных и, если необходимо, записываться в них.

Код программы:

numb = int(input("Введите целое число: "))
min_divider = numb
max_divider = 1
for i in range(numb - 1, 1, -1):
    if (numb % i == 0):
        if (min_divider > i):
            min_divider = i
        if (max_divider < i):
            max_divider = i
print("Минимальный равен:", min_divider)
print("Максимальный равен:", max_divider)

Результат выполнения:

Введите целое число: 63
Минимальный равен: 3
Максимальный равен: 21

Нахождение наименьшего и наибольшего делителя, подсчёт суммы делителей и их количества можно объединить в одну программу на Python. Это не должно вызвать каких-либо проблем или конфликтов, потому что программа работает с 4 независимыми переменными.

Источник

Кстати, можно подсчитать эту самую сумму для всех чисел от 1 до n за линейную сложность.

Надо использовать модифицированное решето Эратосфена, чтобы найти для каждого числа его минимальный простой делитель. Используя эти данные можно для каждого числа найти его минимальный простой делитель в максимальной степени, на которую число делится – один множитель из разложения на простые множители.

Далее, используя эти данные, можно подсчитать сумму всех простых делителей используя формулу S=(p1^(k1+1)-1)/(1-p1)*...*(pm^(km+1)-1)/(1-pm) (тут p1^k1...pm^km – разложение числа на простые множители).

Надо считать эту сумму делителей от меньших чисел к большим (обозначим ее S(n)). Тогда S(n) = S(n/p^k)*(p^k*p-1)/(p-1).

Но это так, для любопытных. Я думаю в вашей задаче достаточно для кадого числа проверять все делители до корня (а оставшиеся делители получаются как n/i, если i – делитель до корня). Надо только аккуратно разобрать случай, когда i = sqrt(n) – тогда второй делитель не надо рассматривать, ибо это вторая копия того же самого.

Источник

Improve Article

Save Article

Like Article

Read

Discuss

Improve Article

Save Article

Like Article

Given an integer number n, find the largest sum of digits in all divisors of n.

Examples :

Input : n = 12 
Output : 6
Explanation:
The divisors are: 1 2 3 4 6 12.
6 is maximum sum among all divisors

Input : n = 68
Output : 14
Explanation: 
The divisors are: 1 2 4 68
68 consists of maximum sum of digit

Naive approach:
The idea is simple, we find all divisors of a number one by one. For every divisor, we compute sum of digits. Finally, we return the largest sum of digits.

Below is the implementation of the above approach:

CPP

#include <bits/stdc++.h>

using namespace std;

int getSum(int n)

{

int sum = 0;

while (n != 0) {

sum = sum + n % 10;

n = n / 10;

}

return sum;

}

int largestDigitSumdivisior(int n)

{

int res = 0;

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

if (n % i == 0)

res = max(res, getSum(i));

return res;

}

int main()

{

int n = 14;

cout << largestDigitSumdivisior(n) << endl;

return 0;

}

Java

import java.util.*;

import java.lang.*;

class GfG

{

public static int getSum(int n)

{

int sum = 0;

while (n != 0)

{

sum = sum + n % 10;

n = n/10;

}

return sum;

}

public static int largestDigitSumdivisior(int n)

{

int res = 0;

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

if (n % i == 0)

res = Math.max(res, getSum(i));

return res;

}

public static void main(String argc[]){

int n = 14;

System.out.println(largestDigitSumdivisior(n));

}

Python3

def getSum( n ):

sum = 0

while n != 0:

sum = sum + n % 10

n = int( n / 10 )

return sum

def largestDigitSumdivisior( n ):

res = 0

for i in range(1, n + 1):

if n % i == 0:

res = max(res, getSum(i))

return res

n = 14

print(largestDigitSumdivisior(n) )

C#

using System;

class GfG

{

public static int getSum(int n)

{

int sum = 0;

while (n != 0)

{

sum = sum + n % 10;

n = n / 10;

}

return sum;

}

public static int largestDigitSumdivisior(int n)

{

int res = 0;

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

if (n % i == 0)

res = Math.Max(res, getSum(i));

return res;

}

public static void Main()

{

int n = 14;

Console.WriteLine(largestDigitSumdivisior(n));

}

PHP

<?php

function getSum( $n)

{

$sum = 0;

while ($n != 0)

{

$sum = $sum + $n % 10;

$n = $n/10;

}

return $sum;

}

function largestDigitSumdivisior( $n)

{

$res = 0;

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

if ($n % $i == 0)

$res = max($res, getSum($i));

return $res;

}

$n = 14;

echo largestDigitSumdivisior($n);

?>

Javascript

<script>

function getSum(n)

{

let sum = 0;

while (n != 0)

{

sum = sum + n % 10;

n = Math.floor(n/10);

}

return sum;

}

function largestDigitSumdivisior(n)

{

let res = 0;

for (let i = 1; i <= n; i++)

if (n % i == 0)

res = Math.max(res, getSum(i));

return res;

}

let n = 14;

document.write(largestDigitSumdivisior(n)

+ "<br>");

</script>

Time Complexity: O(n*log₁₀ (n))
Auxiliary Space: O(1)

An efficient approach will be to find the divisors in O(sqrt n). We follow the same steps as above, just iterate till sqrt(n) and get i and n/i as their divisors whenever n%i==0.
Below is the implementation of the above approach:

CPP

#include <bits/stdc++.h>

using namespace std;

int getSum(int n)

{

int sum = 0;

while (n != 0)

{

sum = sum + n % 10;

n = n / 10;

}

return sum;

}

int largestDigitSumdivisior(int n)

{

int res = 0;

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

if (n % i == 0)

{

res = max(res, getSum(i));

res = max(res,getSum(n / i));

}

return res;

}

int main()

{

int n = 14;

cout << largestDigitSumdivisior(n)

<< endl;

return 0;

}

Java

import java.io.*;

import java.math.*;

class GFG

{

static int getSum(int n)

{

int sum = 0;

while (n != 0)

{

sum = sum + n % 10;

n = n / 10;

}

return sum;

}

static int largestDigitSumdivisior(int n)

{

int res = 0;

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

{

if (n % i == 0)

{

res = Math.max(res, getSum(i));

res = Math.max(res, getSum(n / i));

}

return res;

}

public static void main(String args[])

{

int n = 14;

System.out.println(largestDigitSumdivisior(n));

}

Python3

import math

def getSum(n) :

sm = 0

while (n != 0) :

sm = sm + n % 10

n = n // 10

return sm

def largestDigitSumdivisior(n) :

res = 0

for i in range(1, (int)(math.sqrt(n))+1) :

if (n % i == 0) :

res = max(res, getSum(i))

res = max(res, getSum(n // i))

return res

n = 14

print(largestDigitSumdivisior(n))

C#

using System;

class GFG

{

static int getSum(int n)

{

int sum = 0;

while (n != 0)

{

sum = sum + n % 10;

n = n / 10;

}

return sum;

}

static int largestDigitSumdivisior(int n)

{

int res = 0;

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

{

if (n % i == 0)

{

res = Math.Max(res, getSum(i));

res = Math.Max(res, getSum(n / i));

}

return res;

}

public static void Main()

{

int n = 14;

Console.WriteLine(largestDigitSumdivisior(n));

}

PHP

<?php

function getSum($n)

{

$sum = 0;

while ($n != 0)

{

$sum = $sum + $n % 10;

$n = $n / 10;

}

return $sum;

}

function largestDigitSumdivisior( $n)

{

$res = 0;

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

if ($n % $i == 0)

{

$res = max($res, getSum($i));

$res = max($res, getSum($n / $i));

}

return $res;

}

$n = 14;

echo largestDigitSumdivisior($n);

?>

Javascript

<script>

function getSum(n)

{

var sum = 0;

while (n != 0)

{

sum = sum + n % 10;

n = parseInt(n / 10);

}

return sum;

}

function largestDigitSumdivisior(n)

{

var res = 0;

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

if (n % i == 0)

{

res = Math.max(res, getSum(i));

res = Math.max(res,getSum(n / i));

}

return res;

}

var n = 14;

document.write(largestDigitSumdivisior(n));

</script>

Time Complexity: O(sqrt(n) log n)
Auxiliary Space: O(1) as it is using constant space for variables

Last Updated :
20 Feb, 2023

Like Article

Save Article

Источник

Нахождение делителей числа

Простые делители числа

Сумма делителей

Количество делителей

Максимальный и минимальный делитель

CPP

Java

Python3

C#

PHP

Javascript

CPP

Java

Python3

C#

PHP

Javascript

Вам также может понравиться

Как исправить платежную ведомость на выдачу заработной платы

Как найти вероятность того что событие произойдет

Земли как найти кролики

Добавить комментарий Отменить ответ