Hogyan kell kiszámolni, van erre képlet?

Az biztos, hogy 19*k alakú számokat keresünk. Ha elosztjuk a 100 milliót 19-cel, akkor első körben azt fogjuk tudni, hogy a 19 milyen számokkal lehet megszorozva; 100.000.000:19=~5.263.157, tehát 5.263.157 darab szorzatot kell vizsgálnunk. Ha a 19 a legkisebb prímtényező, akkor az 1, 2, ..., 5.263.157 számok legkisebb prímtényezője is a 19. A megoldáshoz úgy a legegyszerűbb eljutni, hogy kiszedjük közülük azokat, amelyekben a 2; 3; 5; 7; 11; 13; 17 megtalálható prímtényezőként. Ezeket szintén össze tudjuk szedni. A következő lépésben párosával keressük a prímtényezőket, vagyis azon számok számosságát, amelyek 2*3=6-tal, 2*5=10-zel, stb. oszthatóak. Következőnek hármasával, négyesével, ..., hetesével vizsgáljuk, hogy a prímszámokból képzett szorzatok hány számot osztanak. Ha ezeket mind összeszedtük, akkor a szitaformula szerint kivonhatjuk és hozzáadhatjuk a kapott számokat 5.263.157-ből/hez. Amit így kapunk, annyi szám van 100 millióig, amelyekben a legkisebb prímtényező a 19.

Ha esetleg valami nem világos, segítek még.

Nem tudom, hogy ez a reciprokos hozzáadom-kivonom számítás honnan jött, én nem látom bele, hogy jó lenne, ettől még persze lehet jó.

Lehetséges, hogy van ennél egyszerűbb megoldás is, azt szintén nem látom.

A leírásom szerint nincs más dolgod, mint összeszedni azokat a számokat, amelyek oszthatóak az előbb leírt pímtényezőkkel, illetve ezek szorzataival, az viszont egyszerűen kijön úgy, hogy az 5.263.157 számot elosztod a szorzatokkal, és a hányados alsó egészrészét veszed, például a 2*3*7=42-vel osztható számok 5.263.157:42=~125.313-an vannak.

Abban igazad van, hogy "sok" osztást kell így elvégezni (számszerűen 2^7=128-at), majd pedig a szitafromula szerint elvégezni a műveleteket (összeadod a páratlan számú prímtényezővel kapott számokat, és ebből kivonod a páros számú prímtényezővel rendelkezőeket), de teljes mértékben mechanikus számítások, a nagy részéhez számológépet használsz, tehát nem agyonbonyolított.

Még egyszer mondom, ettől még lehetnek más (akár sokkal egyszerűbb) megoldások is, én első körben ezt találtam, ráadásul ez a levezetés középiskolás szinten átlátható és levezethető (még ha sokáig is tart a számolás).

Persze azt sem ártana tudni, hogy milyen problémánál merült fel ez a kérdés, abból lehetne valamire következtetni.