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

First I would suggest to separate the code into two functions: One which computes the sum of odd divisors of a single number, and another which adds the odd divisors of all numbers in a list. Also, use better function names, and add at least a simple doc comment:

def oddDivisorSum(n):
    """Return the sum of odd divisors of n."""
    # ... to do ...


def totalOddDivisorSum(numbers):
    """Return the sum of all odd divisors of all numbers."""
    return sum(oddDivisorSum(n) for n in numbers)

This makes the code more clear, better reusable, and makes it easier to add test cases.

To make the computation faster, two observations help:

1. If $k$ is a divisor of $n$, then $frac{n}{k}$ is also a divisor of $n$.

   This is what Oscar also said, and it allows to restrict the search for divisors to the interval $1dots sqrt n$. The «problem» is that $k$ and $frac{n}{k}$ can have different oddity.

2. If $ k $ is an odd divisor of an even number $n$ then $k$ is also an odd divisor of $frac{n}{2}$.

Therefore, we can remove all even factors of $n$ first, and then find odd divisors in the reduced (odd) number. This makes the code simpler (because all divisors are odd) and faster for even numbers (a smaller $n$ means less trial divisions):

def oddDivisorSum(n):
    """Return the sum of odd divisors of n."""
    while n % 2 == 0:
        n //= 2
    sum = 0
    for k in range(1, int(n ** .5) + 1, 2):
        if n % k == 0:
            sum += k
            if n // k != k:
                sum += n // k
    return sum

Работа с алгоритмами
обработки простой переменной

Цель работы: освоить работу с простой
переменной и алгоритмами их обработки
при решении задач целочисленной
арифметики.

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

Существует целый ряд типовых алгоритмов,
в которых используется простая переменная.
В основном это задачи целочисленной
арифметики. Типовые алгоритмы:

1. Определение
   количества цифр числа.

2. Определение
   суммы цифр числа.

3. Определить,
   является ли заданное число палиндромом.

4. Вывести
   на печать все делители заданного числа.

5. Определить,
   является ли число ‘совершенным’.

1. Определить,
   является ли число простым.

2. Определите
   и напечатайте простые делители числа.

Типовые алгоритмы обработки простой
переменной

Рассмотрим некоторые типовые алгоритмы
обработки простой переменной, на базе
которых решается множество задач,
некоторые из них в дальнейшем будут
рассмотрены. Положим, что в декларативной
части программы описаны следующие
переменные: number, number1, number2 — целые
числа, подлежащие обработке; temp —
переменная для хранения цифры числа;
delit – делители числа; flag –
переменная логического типа, которая
используется для досрочного выхода из
цикла. Для выделения цифры из числа
будем использовать целочисленные
операции div (целая часть) и mod
(целый остаток).

1. Выделение цифр в числе

Реализация:

readln(number);

while number<>0 do

begin

temp:=number mod
10; {выделение цифры из числа}

number:=number
div 10; {уменьшение числа
на один разряд}

end;

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

Реализация:

readln(number);

write(‘
делители числа:
’);

for delit:=2 to number div 2 do

if number mod delit=0 then write(delit, ‘ ‘);

3. Проверка на простоту

Простым является число, которое имеет
только два делителя (1 и само себя). Для
того чтобы определить является ли число
простым, можно подсчитать количество
делителей, для этого нужно использовать
типовой алгоритм нахождение делителей
числа, но можно использовать и более
оптимальный алгоритм, который также
основан на предыдущем алгоритме.

Реализация:

writeln(‘Введите
целое число’);

readln(number);

flag:=
true; {предположим, что
число простое}

delit:=2;

while flag and (delit< =number div
2) do

if number mod delit=0 then
flag:=false

else
delit:=delit+1;

if
flag then writeln (‘число простое‘)

else writeln
(‘число составное’);

4. Нахождение наибольшего общего делителя (нод) двух чисел

Реализация:

writeln(‘Введите
два целых числа’);

readln(number1, number2);

while number1<> number2 do

if number1> number2
then number1:=number1-number2

else number2:=number2-number1;

writeln
(‘НОД чисел
= ’, number1 );

Образцы решения задачи.

Задача № 1.
Определить количество и сумму цифр в
числе.

Анализ
постановки задачи.

Для решения данной задачи воспользуемся
типовым алгоритмом выделения цифр в
числе.

Входные данные.

Число,
подлежащее обработке — number
(тип – целый).

Выходные данные.

Сумма цифр в числе — sum
(тип – целый).

Количество цифр в числе — kol
(тип – целый).

Промежуточные данные.

Переменная для хранения цифры числа
— temp (тип – целый).

Алгоритм.

1. Запросить целое
   число.

2. Обнулить два
   счетчика (для суммы и количества цифр).

3. Выделить цифру из
   числа (использовать операцию целочисленного
   деления — mod).

4. Суммировать
   выделенную цифру числа.

5. Увеличить счетчик
   количества цифр на единицу.

6. Избавиться от
   разряда в числе (использовать операцию
   целочисленного деления — div).

7. Выполнять п. 3-6, до
   тех пор, пока обрабатываемое число не
   равно нулю.

8. Вывести результат
   на печать.

Текст программы

var

number, temp, sum, kol:
integer;

begin

writeln(‘Введите
целое число’);

readln(number);

kol:=0;

sum:=0;

while number<>0 do

begin

temp:=number
mod 10;

sum:=sum+temp; {подсчитывается
сумма цифр
в числе}

kol:=kol+1; {подсчитывается
количество цифр в числе}

number:=number div 10

end;

writeln (‘sum= ‘, sum, ‘kol=
’, kol)

end.

Задача № 2.
Определить является целое число
совершенным.

Анализ постановки
задачи.

Df: Совершенным
называется число, которое равно сумме
всех своих делителей, кроме самого числа
(например: 6=1+2+3).

Исходя из
определения, для решения данной задачи,
будем использовать типовой алгоритм
нахождение делителей числа.

Входные данные.

Число,
подлежащее обработке – number
(тип — целый).

Выходные данные.

Сумма
делителей числа – sum
(тип — целый).

Промежуточные данные.

Переменная для хранения делителя
обрабатываемого числа – delit
(тип – целый).

Алгоритм.

1. Запросить целое
   число.

2. Обнулить счетчик
   суммы.

3. Найти сумму
   делителей числа (типовой алгоритм –
   нахождение делителей числа).

4. Сравнить
   обрабатываемое число с суммой делителей
   числа и вывести соответствующее
   сообщение на печать.

Текст
программы

var

number,
delit, sum: integer;

begin

writeln(‘Введите
целое число’);

readln(number);

sum:=0;

for delit:= 1 to number div 2 do

if
number mod delit =0 then sum:=sum+delit;

if
number=sum then
writeln(‘Заданное число
является совершенным’)

else writeln(‘Заданное
число не является совершенным’)

end.

Задания для самостоятельного решения.

Вариант 1.

1. Дано натуральное число.
   Найти
   первую и последнюю цифры числа.

2. Определить
   количество натуральных трехзначных
   чисел, сумма цифр которых равна заданному
   числу N.

3. Составить
   программу для проверки, можно ли заданное
   натуральное число N
   представить в виде куба простого числа.

Вариант 2.

1. Дано натуральное число.
   Верно
   ли, что сумма цифр данного числа равна
   А (А вводится с клавиатуры).

2. Среди
   двузначных чисел найти те, сумма
   квадратов цифр которых делится на 13.

3. Составить
   программу для проверки, можно ли заданное
   натуральное число N
   представить в виде квадрата простого
   числа.

Вариант 3.

1. Дано натуральное число. Сколько раз
   данная цифра А встречается в данном
   числе (А вводится с клавиатуры).

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

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

Вариант 4.

1. Дано натуральное число.
   Верно
   ли, что в данном числе сумма цифр больше
   В, а само число делится на В (В вводится
   с клавиатуры).

2. Квадраты
   некоторых трехзначных чисел оканчиваются
   тремя цифрами, которые как раз и
   составляют исходные числа. Написать
   программу поиска таких чисел.

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

Вариант 5.

1. Из данного натурального
   числа удалить все цифры А (А вводится
   с клавиатуры).

2. Среди
   трехзначных чисел найти те, сумма цифр
   которых делится на 9.

3. Составьте
   программу разложения натурального
   числа N на простые
   множители.

Вариант 6.

1. Дано натуральное число.
   Верно
   ли, что сумма четных цифр больше сумма
   нечетных цифр данного числа.

2. Квадраты
   некоторых двухзначных чисел оканчиваются
   двумя цифрами, которые как раз и
   составляют исходные числа. Написать
   программу поиска таких чисел.

3. Заданы
   два целых числа М, N.
   Определить, больше ли сумма простых
   делителей числа М, произведения составных
   делителей числа N.

Вариант 7.

1. Дано натуральное число.
   Верно
   ли, что произведение нечетных цифр
   данного числа меньше некоторого
   заданного числа.

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

3. Задано
   целое число N. Найти
   ближайшее к нему совершенное число.

Вариант 8.

1. Дано натуральное число не
   менее шести разрядов. Найти
   сумму цифр данного числа стоящих на
   нечетных местах.

2. Составьте
   программу определения наименьшего
   общего кратного двух натуральных
   чисел.

3. Задано
   целое число N. Определить
   количество различных цифр числа N.

Вариант 9.

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

2. Задано
   целое положительное число N меньшее
   32000. Написать программу, определяющую,
   все ли цифры числа N меньше или равны
   4. Если это условие выполняется, найти
   сумму этих цифр.

1. Вывести
   на печать сто простых чисел.

Вариант 10.

1. Найти произведение четных делителей
   натурального числа.

2. Найти сумму целых
   чисел из промежутка от 1 до 200, у
   которых ровно 5 делителей.

3. Даны
   натуральные числа N, M.
   Получить сумму M последних
   цифр числа N.

Контрольные вопросы:

Чему будет равно значение переменной
с в результате выполнения
последовательности команд присваивания?

с:=12; c:=6+c
div 3*2;

Чему будет равно значение переменной
t в результате выполнения
последовательности команд присваивания?

r:=7; t:=3; t:=r+t; r:=t-r; t:=t-r;

Сколько раз выполнится тело цикла во
фрагменте алгоритма:

b:=true;
x:=64;

while b
do begin

b:=(x>=4);

x:=x div 6+2

end;

4. Сколько раз
выполнится тело цикла во фрагменте
алгоритма:

q:=27;
p:=36;

while q
div 5= p div 7 do begin

q:=q+2;

p:=p+3

end;

5. Укажите, чему
будет равно значение v
после выполнения фрагмента алгоритма,
если вводится целое значение n,
равное 125…

с:=100;
v:=0;

while n>0 do begin

v:=v+n div c;

n:=n mod c;

c:=с div 10

end;

6. Вычислите
результат выполнения фрагмента алгоритма:

n:=10;

s:=0;

for i:=1 to n div 2 do

s:=s+ n
mod i;

7. Вычислите
результат выполнения фрагмента алгоритма:

n:=19;

s:=0;

for i:= 2
to n mod 7 do begin

s:=s+
n div i;

n:= n
div 2;

end;

8. Какую операцию
целочисленного деления необходимо
использовать для получения цифры числа?

9. Почему
целесообразнее выделять цифры из числа
справа на лево, а не слева на право?

10. Какой алгоритм
необходимо применить, если все-таки
цифры из заданного числа выделять слева
на право?

5

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

1.

program raf105;

var a,b,c:integer;

begin

write(‘Введите 3 числа: ‘);

readln(a,b,c);

if (a<b) and (a<c)

 then writeln(‘Произведение 2 наибольших чисел: ‘,b*c);

if (b<a) and (b<c)

 then writeln(‘Произведение 2 наибольших чисел: ‘,a*c);

if (c<b) and (c<a)

 then writeln(‘Произведение 2 наибольших чисел: ‘,b*a);

end.

2.

а)

program raf105;

var a,i,b:integer;

begin

write(‘Введите число: ‘);

readln(a);

for i:=1 to a do

 if ((a mod i)=0) and ((i mod 2)<>0)

   then b:= b+i;

writeln(‘Сумма нечётных делителей введённого числа: ‘,b);

end.

б)

program raf105;

var a,a2,i,j,b:integer;

begin

write(‘Введите меньшее число: ‘);

readln(a);

write(‘Введите большее число: ‘);

readln(a2);

for j:=a to a2 do

begin

 for i:=1 to j do

   if ((j mod i)=0) and ((i mod 2)<>0)

     then b:= b+i;

writeln(‘Сумма нечётных делителей числа ‘,j,’ равна: ‘,b);

b:= 0;

end;

end.

Язык программирования PascalABC

сумма t(n) + s(n) будет нечетной, только при условии, что t(n) и s(n) имеют противоположную четность, т.е:

• t(n) — четное число, а s(n) — нечетное число, либо
• t(n) — нечетное число, а s(n) — четное число

1.может ли число n — быть нечетным?

в данном случае — все делители числа Х — являются нечетными числами

• если t(n) — нечетное число, то s(n) — также нечетное число (сумма нечетного кол-ва нечетных чисел — всегда является нечетным числом)
• если t(n) — четное число, то s(n) — также четное число (сумма четного кол-ва нечетных чисел — всегда является четным числом)

таким образом, t(n)+s(n) — будет всегда является четным числом

следовательно n — не может быть нечетным числом

2.рассмотрим вариант, когда число n — является четным числом

тогда n = Н * 2^k

где Н — нечетное число, k — натуральное число

вариант 2.1 — если t(n) — нечетное число (т.е n имеет нечетное кол-во делителей)

тогда n — является полным квадратом натурального числа

но тогда Н — также является полным квадратом, (т.к числа Н и 2^k — не имеют общих делителей)

значит Н — также имеет нечетное кол-во делителей (при этом все делители числа Н — обязательно нечетные)

следовательно число n — имеет нечетное кол-во нечетных делителей (а также некоторое кол-во четных делителей)

значит s(n) — также будет нечетным числом

т.е в данном варианте: t(n)+s(n) — обязательно будет являться четным числом, но это противоречит условию Задачи

вариант 2.2 — если t(n) — четное число (т.е n имеет четное кол-во делителей)

тогда для того, чтобы t(n) + s(n) было нечетным числом, необходимо, чтобы:

s(n) — являлось нечетным числом

т.е сумма всех делителей числа n — является нечетным числом, это возможно только при условии, если:

число n — имеет нечетное кол-во нечетных делителей

вспоминаем, что n = Н * 2^k

следовательно:

число Н — также имеет нечетное кол-во делителей, т.к все нечетные делители числа n — это делители числа Н

значит Н — является полным квадратом, т.е Н = z² (где z — натуральное нечетное число)

вспоминаем, что число n имеет четное число делителей — значит: n — не является полным квадратом, следовательно 2^k — не является полным квадратом, а это возможно только при условии, если k — нечетное число

ответ на вопрос А:

сумма t(n)+s(n) будет нечетной, при условии, если:

n = z² * 2^k (где z и k — натуральные нечетные числа)

последняя цифра числа t(n) равна 3 — значит t(n) — нечетное число

при ответе на вопрос А, было доказано, что:

если t(n) — нечетное число, то s(n) — также будет нечетным числом

т.е последней цифрой числа s(n) не может быть 2

рассмотрим вариант:

n = 3

данное число имеет 2 делителя: 1 и 3

при этом t(n)= 2 (простое число) s(n)= 4 (не является простым числом)

Ответ на вопрос В1): НЕТ