Комбинаторна задача

[justme.h]

Колко са четирицифрените числа, които не се делят на никое едноцифрено число освен 1?

[Knowledge Greedy]

Всички четирицифрени числа са 9999-999=9000.
От тях ще извадим всички онези четирицифрени, които се делят на 2, на 3, на 5 и на 7.
Те са съответно 4500, 3000, 1800 и 1285.
Но при това сме извадили по два пъти тези, които се делят:
на 6 (-на 2 и 3 едновременно),
на 10 (-на 2 и 5 едновременно),
на 14 (- на 2 и 7 едновременно),
на 15 (- на 3 и 5 едновременно),
на 21 (- на 3 и 7 едновременно),
на 35 (на 5 и 7 едновременно).
Значи трябва да добавим 1500+900+642+600+428+257.
Сега обаче направихме противоположното - имаме в повече такива числа, които се делят едновременно:
на 2, 3 и 5 (т. е. на 30) - те са 300;
на 2, 3 и 7 (т. е. на 42) - те са 214;
на 2, 5 и 7 (т. е. на 70) - те са 128;
на 3, 5 и 7 (т. е. на 105) - те са 85.
Изваждаме 300+214+128+85
При последната операция отново не всичко е както трябва - премахнали сме тези, които се делят едновременно на 2, 3, 5 и 7. Такива числа има 4.
Добавяме 4.
В резултат получаваме
9000-(4500+3000+1800+1285)+(1500+900+642+600+428+257)-(300+214+128+85)+4 = 2019 четирицифрени числа, които не се делят на едноцифрени числа, по-големи от 1.