Question

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

Answer 1

Ответ: 1358114

Объяснение:

1. Делители числа 2019:

2019|3

673|673

    1|

2.  Взаимно простыми с 2019 являются все числа, не превосходящие 2019. не включая числа, кратные 3 и 673.

3. Имеется 673 числа, кратных 3, и число 673 - простое.

 4. Сумма всех чисел от 1 до 2019, вычисляется методом Гауса, парами:

1-я пара: 1+2019=2020

всего пар: 2019/2=1009(ост.1) - значит среднее число 1010 пары не имеет.

Сумма всех чисел = 2020*1009+1010=2039190

5. Сумма всех чисел, кратных 3 вычисляется по формуле суммы членов ариaметической прогрессии:

a₁=3; d=3

а₆₇₃=2019 - известно, потому, что последний член заданного множества натуральных чисел от 1 до 2019, кратен 3. (2019/3=673)

S₆₇₃=(3+2019)|2*673

S₆₇₃=680403

 6. Сумма всех натуральных чисел, не превосходящих 2019 и взаимно простых с ним:

      2039190-680403-673=1358114

Answer 2

Для решения этой задачи можно использовать алгоритм Эйлера (алгоритм подсчета количества взаимно простых чисел с заданным числом).

1. Инициализируем переменную сумма равной 0.
2. Для каждого числа n от 1 до 2019, выполняем следующие шаги: a. Инициализируем переменную взаимно_простые равной True. b. Для каждого числа i от 2 до n-1, выполняем следующие шаги: i. Если n и i имеют общий делитель (число n не является взаимно простым с i), устанавливаем взаимно_простые в False и выходим из цикла. c. Если взаимно_простые равно True, добавляем n к переменной сумма.
3. Выводим значение переменной сумма.

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

pythonCopy code
сумма = 0

for n in range(1, 2020):
    взаимно_простые = True
    for i in range(2, n):
        if n % i == 0:
            взаимно_простые = False
            break
    if взаимно_простые:
        сумма += n

print(сумма)

Запустив этот код, получаем ответ: 993.