Данную задачу я увидел благодаря автору канала
Который её и решил. Но у меня зачесались руки её оптимизировать, тем более что когда я встречаю задачи, связанные с математикой, они вводят меня в ступор, а тут, значит, случился редкий момент просветления.
Задача
Если выписать все натуральные числа меньше 10, кратные 3 или 5, то получим 3, 5, 6 и 9. Сумма этих чисел равна 23.
Найдите сумму всех чисел меньше 1000, кратных 3 или 5.
Решение
Автор действует напрямую – циклом от 1 до 999, с проверкой, кратно число 3 или 5. Если кратно, оно прибавляется к сумме:
Я бы тоже так и делал, но здесь сразу видно одну лазейку для оптимизации цикла. Нет смысла проверять каждое число на кратность 3, если мы знаем, что кратно будет каждое 3-е. Значит, можно переписать цикл так, чтобы прибавлять к счётчику не 1, а 3. Придётся только сделать два разных цикла для 3 и 5:
Правда, результат получился неправильный, но здесь его уже нет смысла исправлять, потому что этот код немедленно даёт новую пищу для размышлений.
Если в цикле к счётчику прибавляется по 3 до 999, то очевидно, что таких прибавлений всего будет 999/3. Аналогично для 5.
Это значит, что циклы с проверкой на кратность вообще не нужны. Нужно просто найти сумму последовательности из N элементов: 3, 6, 9, 12, ..., где N это 999/3. И добавить ещё одну сумму из M элементов: 5, 10, 15, 20, ..., где M это 999/5.
Сумма последовательности 1, 2, 3, 4... N вычисляется как (1+N)*N/2. Для 3 эту сумму умножаем на 3, для 5 на 5.
Итого, осталось только вычислить две суммы и сложить их:
И опять неверный результат. Надо сказать, он заставил меня липко пропотеть, но причина оказалась банальной. Есть числа, которые одновременно кратны и 3, и 5. То есть они кратны 15. Прибавляются они к сумме по два раза – сначала за 3-ку, потом за 5-ку. Что неправильно, они должны прибавляться только один раз.
Поэтому я дополнительно вычисляю третью сумму чисел, кратных 15, и вычитаю её из общей суммы:
Вот теперь результат правильный. Скорость я замерять не буду, потому что и так очевидно, что здесь сложность O(1), а в варианте с циклами O(N), поэтому здесь быстрее.
Ссылка на онлайн-компилятор языка C с текстом программы:
https://onlinegdb.com/p6UfpXvKB
Далее буду пробовать решать следующие задачи, но думаю, там будет уже гораздо печальнее для меня :)
Вся подборка задач: