Анализ алгоритма
Обозначим через σ(n) сумму всех делителей числа n .
· Если n = p (p простое ), то σ ( n) = 1 + p;
· Если n = p a ( p простое ), то σ ( p a ) = 1 + p + p 2 + p 3 + … + p a = ;
Функция σ ( n) является мультипликативной . Если n = , то
σ ( n) = σ ( ) * σ ( ) * … * σ( ) =
Указанную сумму можно записать также в виде
Пример
n = 239 простое, σ( 239 ) = 1 + 239 = 240.
n = 24 = 2 3 * 3, σ ( 24 ) = σ ( 2 3 ) * σ ( 3 ) = (1 + 2 + 4 + 8) * (1 + 3) = 15 * 4 = 60.
Вычислим сумму делителей для n = 24 непосредственно: σ ( 24 ) =
1 + 2 + 3 + 4 + 6 + 8 + 12 + 24 =
1 + 2 + 4 + 8 + 3 * (1 + 2 + 4 + 8) =
(1 + 2 + 4 + 8) * (1 + 3) = 15 * 4 = 60
Реализация алгоритма
Читаем входное значение n.
В переменной i перебираем все простые делители числа n (по условию задачи они не более 1000). Вычисляем сумму делителей числа n по указанной в анализе задачи формуле.
Пусть i – простой делитель n. Находим максимальную степень a, для которой i a делит n.
После выполнения цикла p = i a +1 . Умножаем res на .
res *= (p — 1) / (i — 1);
printf( «%lld\n» ,res);
Java реализация
import java.util.*;
class Main
public static void main(String[] args)
Scanner con = new Scanner(System.in);
long n = con.nextLong();
long res = 1;
for ( int i = 2; i
while (n % i == 0)
res *= (p — 1) / (i — 1);
Количество делителей, сумма делителей
Если a и b взаимно просты, то каждый делитель произведения ab может быть единственным образом представлен в виде произведения делителей a и b, и обратно, каждое такое произведение является делителем ab. Отсюда следует, что функция [math]~\tau[/math] мультипликативна:
[math] ~\tau(ab) = \tau(a) \tau(b) [/math]
Пусть [math] a = ^ ^ \ldots ^[/math] — каноническое разложение числа a, то в силу мультипликативности
Но положительными делителями числа [math]p_i^[/math] являются [math]~\alpha_i+1[/math] чисел [math]1, p_i, \ldots, p_i^[/math] .
[math] ~\tau(n) = (\alpha_1+1) (\alpha_2+1) \ldots (\alpha_k+1) [/math]
Сумма делителей
| Определение: |
| Функция [math]~\sigma (a) [/math] определяется как сумма делителей натурального числа a: [math] ~\sigma (a) = \sum_ |
Функция [math]~\sigma (a) [/math] мультипликативна по тем же соображениям, что и [math]~\tau (a) [/math]
[math] ~\sigma (ab) = \sigma (a) \sigma(b) [/math]
Найти сумму делителей натурального числа
Задача 2.16
Дано натуральное число N. Вывести на экран сумму его делителей. Число 1 считается делителем любого натурального числа. Число N не является делителем числа N.
Эту задачу довольно часто задают в контрольных и прочих студенческих делах. Задача несложная. Однако на её примере начинающие могут кое-чему научиться.
Алгоритм решения довольно простой:
- Перебираем в цикле все возможные целые числа от 1 до числа N.
- Каждый раз пытаемся делить число N на текущее число. Если оно делится без остатка, то текущее число является делителем числа N. Прибавляем его к итоговой сумме.
Разумеется, сначала подготавливаем необходимые переменные.
Ну а чтобы задачка была поинтереснее, предлагаю дополнительно сделать так, чтобы на экран была выведена не только итоговая сумма делителей числа N, но и сами делители.
Решения на Паскале и С++ представлены ниже. Если кто забыл, что такое натуральное число, то см. здесь.
Краткое описание программы:
- Обнуляем переменную Sum, в которой у нас будет итоговая сумма делителей.
- Получаем случайное значение и записываем его в переменную N.
- Затем запускаем цикл от 1 до N и в каждой итерации цикла вызываем нашу функцию ThisDivider(N, i), которая возвращает TRUE, если число i является делителем числа N. Саму функцию описывать не буду, потому что она достаточно простая.
- Если число i является делителем числа N, то к переменной Sum мы прибавляем число i, а к строке Str присоединяем строковое представление числа i, предварительно преобразовав это число в строку. Так мы получаем строку, которая содержит все делители числа N.
- Ну и в конце выводим всё на экран.
Обратите внимание, что для использования функции преобразования числа в строку в Паскале надо подключить модуль SysUtils, а в С++ — .
Также обратите внимание на то, как мы преобразуем число в строку на С++. Делается это довольно замысловато. И это ещё не самый сложный способ. В Паскале же всё просто и интуитивно понятно. Ну а в С++, как всегда, всё через зад.
Правда, начиная со стандарта С++ 2011 года (вроде с него), появилась более понятная и приятная функция to_string(). Но плохая новость заключается в том, что далеко не все средства разработки (особенно бесплатные) поддерживают этот стандарт. Поэтому я не стал использовать эту функцию в своей программе.
Решение задачи 2.16 на Паскале
program t216; uses SysUtils; //Подключить этот модуль //**************************************************************** // ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ //**************************************************************** var i : WORD; //Индекс N : WORD; //Число Sum : DWORD = 0; //Сумма Str : string = »; //Строка для делителей //**************************************************************** // ФУНКЦИИ И ПРОЦЕДУРЫ //**************************************************************** //**************************************************************** // Функция принимает число и возможный делитель. // ВХОД: Num — число // Del — возможный делитель // ВЫХОД: TRUE — если Del является делителем числа Num //**************************************************************** function ThisDivider(Num, Del : WORD) : boolean; begin if Del = Num then begin Result := FALSE; Exit; end; Result := (Num mod Del) = 0; end; //**************************************************************** // ОСНОВНАЯ ПРОГРАММА //**************************************************************** begin Randomize; //Запустить генерацию случайных чисел N := Random(High(N)); //Получить случайное число WriteLn(‘N = ‘, N); for i := 1 to N do //В цикле проверить возможные делители begin if ThisDivider(N, i) then //Если это делитель, то begin Sum := Sum + i; //прибавить его к сумме Str := Str + IntToStr(i) + ‘ ‘; end; end; //Вывести на экран WriteLn(‘Dividers : ‘, Str); WriteLn(‘Sum of the divisors = ‘, Sum); WriteLn(‘The end. Press ENTER. ‘); ReadLn; end.