Как найти сумму делителей числа
Перейти к содержимому

Как найти сумму делителей числа

  • автор:

Найти сумму делителей натурального числа

Основы программирования 2.0

Задача 2.16
Дано натуральное число N. Вывести на экран сумму его делителей. Число 1 считается делителем любого натурального числа. Число N не является делителем числа N.

Эту задачу довольно часто задают в контрольных и прочих студенческих делах. Задача несложная. Однако на её примере начинающие могут кое-чему научиться.

Алгоритм решения довольно простой:

  1. Перебираем в цикле все возможные целые числа от 1 до числа N.
  2. Каждый раз пытаемся делить число N на текущее число. Если оно делится без остатка, то текущее число является делителем числа N. Прибавляем его к итоговой сумме.

Разумеется, сначала подготавливаем необходимые переменные.

Ну а чтобы задачка была поинтереснее, предлагаю дополнительно сделать так, чтобы на экран была выведена не только итоговая сумма делителей числа N, но и сами делители.

Решения на Паскале и С++ представлены ниже. Если кто забыл, что такое натуральное число, то см. здесь.

Краткое описание программы:

  1. Обнуляем переменную Sum, в которой у нас будет итоговая сумма делителей.
  2. Получаем случайное значение и записываем его в переменную N.
  3. Затем запускаем цикл от 1 до N и в каждой итерации цикла вызываем нашу функцию ThisDivider(N, i), которая возвращает TRUE, если число i является делителем числа N. Саму функцию описывать не буду, потому что она достаточно простая.
  4. Если число i является делителем числа N, то к переменной Sum мы прибавляем число i, а к строке Str присоединяем строковое представление числа i, предварительно преобразовав это число в строку. Так мы получаем строку, которая содержит все делители числа N.
  5. Ну и в конце выводим всё на экран.

Обратите внимание, что для использования функции преобразования числа в строку в Паскале надо подключить модуль 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.

Решение задачи 2.16 на С++ #include #include #include //Подключить этот файл using namespace std; //**************************************************************** // ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ //**************************************************************** unsigned short int N; //Число unsigned long int Sum = 0; //Сумма ostringstream Str; //Строка для делителей //**************************************************************** // ФУНКЦИИ И ПРОЦЕДУРЫ //**************************************************************** //**************************************************************** // Функция принимает число и возможный делитель. // ВХОД: Num — число // Del — возможный делитель // ВЫХОД: TRUE — если Del является делителем числа Num //**************************************************************** bool ThisDivider(unsigned short int Num, unsigned short int Del) < if (Del == Num) return(false); return(0 == (Num % Del)); >//**************************************************************** // ОСНОВНАЯ ПРОГРАММА //**************************************************************** int main(int argc, char *argv[]) < srand(time(0)); //Запустить генерацию случайных чисел N = rand() % USHRT_MAX; //Получить случайное число Str.clear(); cout

Анализ алгоритма

Обозначим через σ(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);

Найдите сумму и количество делителей натурального числа?

Числовые функции
Количество всех натуральных делителей натурального числа n обозначается σ0(n). Сумма всех натуральных делителей числа n обозначается σ1(n).

Дано натуральное n≤109.

Выведите σ0(n) и σ1(n).

Данную задачу рекомендуется решать путём перебора всех делителей числа до n−−√.

#include #include #include using namespace std; int main() < int n,c=0,s=0; cin >> n; for (int i = 1; i if (i == sqrt(n) and n % i == 0) < c += 1; s += i; >> cout Помогите пожалуйста. Сайт пишет что программа выдаёт неверный ответ
  • Вопрос задан более двух лет назад
  • 3246 просмотров

Найти сумму простых делителей числа N

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

#include #include // Функция проверки числа на простоту bool isPrime(int n) < for(int i = 2; i * i > return true; > int main(void) < // Наше входное значение int input = 122; // Сразу инициализируем сумму двойкой, если наше число чётное, // иначе инициализируем нулём unsigned long long sum = input % 2 ? 0ULL : 2ULL; // Цикл начинается с 3, потому что двойку мы уже учли в инициализации суммы // и теперь удобно идти только по нечётным числам for (int currentDivisor = 3; currentDivisor > printf("Sum: %llu\n", sum); return 0; > 

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *