Hány olyan legfeljebb 4 jegyű szám (poz. Egész) van amelynek nincs 1 jegyű prím osztója?

Számoljuk össze azokat, amiknek van egyjegyű prímosztója, erre a logikai szitát alkalmazzuk.

2-vel oszthatók: [9999/2] = 4999-en vannak,

3-mal oszthatók: [9999/3] = 3333-an,

5-tel oszthatók: [9999/5] = 1999-en,

7-tel oszthatók: [9999/7] = 1428-an,

összesen 11 759-en, viszont kétszer számoltuk azokat, amiknek 2 különböző egyjegyű prímosztója van, ő közülük

a 2*3 = 6-tal oszthatók 1666-an,

a 2*5 = 10-zel oszthatók 999-en,

a 2*7 = 14-gyel oszthatók 714-en,

a 3*5 = 15-tel oszthatók 666-an,

a 3*7 = 21-gyel oszthatók 476-an,

az 5*7 = 35-tel oszthatók 285-en,

összesen 4806-an vannak, így ezeknek a számát le kell majd vonni a 11 759-ből. Viszont így a kelleténél többször vonjuk le azokat, amiknek 3 különböző egyjegyű prímosztójuk van, ők

a 30-cal oszthatók, akik 333-an vannak,

a 42-vel oszthatók, akik 238-an,

a 70-nel oszthatók, akik 142-en és

a 105-tel oszthatók, akik 95-en,

összesen 808-an vannak, az ő számukat vissza kell majd adni, viszont így a kelleténél eggyel többször adjuk hozzá azokat, akik mind a 4 egyjegyű prímmel oszthatók, és

[9999/(2*3*5*7)] = 47-en vannak, tehát 47-et le kell majd vonni.

Tehát összesen 11 759 – 4806 + 808 – 47 = 7714 olyan legfeljebb négyjegyű pozitív egész szám van, aminek van egyjegyű prímosztója.

A legfeljebb négyjegyű pozitív egész számok 9999-en vannak, ebből 7714-nek van egyjegyű prímosztója, így 9999 – 7714 = 2285-nek nincs.

(Ha nem számoltam el semmit. Tessék ellenőrizni!)

Ha valaki szereti a programozást, akkor ezt is lehet bogarászni (C-ben értendő):

#include <stdio.h>

int fv(int n){

int i, A[] = {2,3,5,7,0};

for (i=0; A[i]; i++) if(!(n%A[i])) return 1;

return 0;}

int main(){

int i, db = 0;

for (i=1; i<1e4; i++) if(!fv(i)) db++;

printf("%d\n",db);

return 0;}

/*VEGE*/

Ez is 2285-öt ad vissza, viszont könnyen lehet értelemszerűen módosítgatni.