Решение задачи Числа с Acmp

С пояснением   Просмотров: 65


Задано натуральное число N. Требуется написать программу, которая находит количество натуральных чисел, не превышающих N и не делящихся ни на одно из чисел 2, 3, 5.


Код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    cout << n - (n/2 + n/3 + n/5) + (n/6 + n/10 + n/15) - n/30;
    return 0;
}

         


Несмотря на её сложность задачу можно решить одной формулой.

Количество чисел, делющихся на 2 - n/2;
Количество чисел, делющихся на 3 - n/3;
Количество чисел, делющихся на 5 - n/5;
Количество чисел, делющихся одновременно на 5 и 3 и 2 - n/30;

Если мы вычтем из n вышеуказанные числа, т.е n - (n/2 + n/3 + n/5 + n/30), мы получим примерное решение. Примерно потому, что есть такие чиcла, которые мы вычли дважды. Это числа, которые одновременно делятся на:

2 и 3 => 2 * 3 => 6
2 и 5 => 2 * 5 => 10
3 и 5 => 3 * 5 => 15


Итак, у меня получилась такая формула:
$$ n - (\frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \frac{n}{30}) + (\frac{n}{6} + \frac{n}{10} + \frac{n}{15}) $$


Комментарии

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