Практика: Цикл для каждого числа

Четыре задачи, в которых внешний цикл идёт по числам от 1 до N, а внутри него — цикл по цифрам или делителям каждого числа. Какой внутренний цикл успеет, решает ограничение на N.

• Количество делителей: N ≤ 3000, поэтому перебор всех d от 1 до i — около 4,5 · 10⁶ шагов: простой цикл подходит.
• Количество чисел с заданной суммой цифр: отрезайте цифры от копии i, а не от самого i. N до 10⁶: не больше 7 цифр в каждом, около 7 · 10⁶ шагов.
• Список простых чисел печатает количество до самих простых. Складывайте простые в вектор через push_back, потом выведите его size() и сам вектор. Проверка на простоту останавливается на d * d <= x и на первом найденном делителе. При N = 1 весь вывод — 0.
• Наибольшее количество делителей: N до 10⁵, поэтому перебор всех d до x для каждого x — около 5 · 10⁹ шагов, слишком медленно. Считайте делители парами, d и x / d, пока d * d <= x, и учитывайте d один раз, когда d * d == x. Чтобы среди победителей остался наименьший, заменяйте лучший результат только строго большим количеством (>).