Hány olyan 1000-nél kisebb természetes szám van, amely nem osztható sem 3-mal, sem 5-tel, sem 7-tel?

Van 999 természetes szám (most a 0-át nem vettem be, sose tudom, hogy azt kell-e, de most mindegy is, mert az osztható lenne).

Először nézzük azokat, amik OSZTHATÓAK 3-mal vagy 5-tel vagy 7-tel:

3-mal osztható van 333 darab (3-tól 999-ig)

5-tel: 199 (5-től 995-ig)

7-tel: 142 (7-től 994-ig. Mivel 999=142·7+5)

Ez 333+199+142 darab. De így vannak olyanok, amiket kétszer is beszámoltunk:

- 3-mal és 5-tel is oszthatók: 66 (999=66·15+9)

- 3-mal és 7-tel is: 47 (999=47·21+12)

- 5-tel és 7-tel is: 23 (999=28·35+19)

Vagyis ezeket egyszer ki kell hagyni. Tehát amik oszthatóak az (333+199+142)−(66+47+23) darab. Viszont vannak olyanok, amik mindhárommal oszthatók, azokat egyrészt 3-szor beszámoltuk, másrészt most mindegyik párral (tehát 3-szor) kihagytuk, vagyis egyszer még be kell őket számolni. Ezek:

- 3·5·7=105, ezzel oszthatók: 999=9·105+54, vagyis 9 olyan van.

Tehát összesen ennyi olyan van, amik oszthatóak:

(333+199+142)−(66+47+23)+9

Vagyis amik NEM oszthatóak, azok ennyien vannak:

999 − (333+199+142−(66+47+23)+9)

A módszer, amit az első válaszoló használt az a "logikai szita formula":

[link]