7. Zadatak

Prvo rješenje.

Brojeva manjih od $1000$ koji su djeljivi s $2$ je

$$\left\lfloor\frac{999}{2}\right\rfloor=499,$$

djeljivih s $3$ je $\left\lfloor\frac{999}{3}\right\rfloor=333$, a djeljivih s $5$ je $\left\lfloor\frac{999}{5}\right\rfloor=199$.

Djeljivih s $6$ ima $\left\lfloor\frac{999}{6}\right\rfloor=166$, djeljivih s $10$ ima $\left\lfloor\frac{999}{10}\right\rfloor=99$, djeljivih s $15$ ima $\left\lfloor\frac{999}{15}\right\rfloor=66$, a djeljivih s $30$ ima $\left\lfloor\frac{999}{30}\right\rfloor=33$.

Ukupan broj brojeva manjih od $1000$ koji su djeljivi s $2$ ili s $3$ ili s $5$ je

$$499+333+199-166-99-66+33=733.$$

Ostalih brojeva ima

$$999-733=266.$$

Među njima su svi prosti brojevi manji od $1000$ osim brojeva $2,3,5$, ukupno njih $168-3=165$. Među preostalim brojevima je i broj $1$ koji nije ni prost ni složen.

Stoga je ukupan broj naizgled–prostih brojeva

$$266-165-1=100.$$

Drugo rješenje.

Naizgled–prosti brojevi su oblika

$$p^2,p^3,p^4,\ldots,pq,pq^2,pq^3,pq^4,\ldots,p^2q^2,p^2q^3,p^2q^4,\ldots,\ldots,pqr,pqr^2,\ldots,$$

gdje su $p,q,r,\ldots$ prosti brojevi veći od $5$.

Vrijedi $7^4>1000$ i $7\cdot11\cdot13=1001>1000$. Provjeravat ćemo koje sve vrijednosti mogu imati brojevi $p,q$ za koje prethodni oblici daju naizgled–proste brojeve manje od $1000$.

Broj $p^2$ manji je od $1000$ za

$$p\in\{7,11,13,\ldots,31\},$$

što daje $8$ brojeva.

Broj $p^3$ manji je od $1000$ za $p=7$, dakle daje $1$ broj.

Broj $p^2q$ manji je od $1000$ za

$$(p,q)\in\{(7,11),(7,13),(7,17),(7,19),(11,7)\},$$

što daje $5$ brojeva.

Dalje brojimo koliko ima naizgled–prostih brojeva oblika $pq$:

$$\begin{aligned} p=7,&\quad q\in\{11,13,\ldots,139\} &&\text{daje 30 brojeva},\\ p=11,&\quad q\in\{13,\ldots,89\} &&\text{daje 19 brojeva},\\ p=13,&\quad q\in\{17,\ldots,73\} &&\text{daje 15 brojeva},\\ p=17,&\quad q\in\{19,\ldots,53\} &&\text{daje 9 brojeva},\\ p=19,&\quad q\in\{23,\ldots,47\} &&\text{daje 7 brojeva},\\ p=23,&\quad q\in\{29,\ldots,43\} &&\text{daje 5 brojeva},\\ p=29,&\quad q=31 &&\text{daje 1 broj}. \end{aligned}$$

Dakle, ukupno je $100$ naizgled–prostih brojeva manjih od $1000$.