Сумма диапазона LCM от 1 до 10 ^ 9
Итак, первый курс программирования, первое неклассифицированное задание:
В C ++ для диапазона чисел от 1 до 1 миллиарда найдите сумму чисел, которые делятся (без остатка) на все от 1 до 99. Как мне это сделать? Как мне найти наименьшее число, делимое на 1:99?
редактировать: это не hw, чтобы быть включенным, просто кое-что, чтобы думать. Я бы попробовал какой-то тип векторизации в matlab, но это мой первый день, когда я пытаюсь использовать c ++, поэтому я понятия не имею, я только что узнал, как инициализировать переменную.
Решение
// In pseudocode a very basic algorithm:
main
for i: 1 to 1000000000
if (TestValue(i))
Output(i)
TestValue(i)
for j: 1 to 99
if j does not divide i evenly
return false
return true
Конечно, это не будет очень эффективным. Вы можете заметить, что если число делится поровну на все числа от 1 до 99, то оно должно делиться на множество простых множителей в 1..99. Например, в 1..19 основными факторами являются: 2, 2, 2, 2, 3, 3, 5, 7, 11, 13, 17, 19. Если что-то делится равномерно на все числа 1..19, то он должен быть равномерно делим на 2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 * 17 * 19 = 232792560. Найти все числа от 1 до 1000000000, которые делятся на 1..19 Я нашел бы все числа от 1 до 1000000000, которые вместо этого делятся на 232792560.
Другие решения