ALG12

312 Rozdział 14. Zadania różne

14.2.Rozwiązania

Zad. 14-1

Do rozwiązania zadania (a) będziemy potrzebowali funkcji zwracającej nam pierwszą całkowitą liczbę x spełniającą warunek x*x<n:

erastot.cpp

inline int sqrt_int(int n)

(return (int)sqrt((double)n)/l;ł

(Wykorzystujemy fakt. że dzielenie całkowite w C++ obcina część ułamkową).

Odpowiedź na pytanie, „czy n jest liczbą pierwszą?”, sprowadza się do sprawdzenia, czy istotnie dzieli się ona tylko przez / i przez siebie samą:

int pierwsza(int n)

(

// czy n jest liczba pierwsza? int limes=sqrt_int(n) ;

for(int i=2; n!=(n/i)*i SS i<=limes;i++); if (i>limes)

return 1;    // tak, liczba pierwsza

else

return 0; II nie, "zwyczajna" liczba

)

Nieco bardziej skomplikowana jest realizacja „sita Erastotenesa” (b).

Problemem jest konieczność deklaracji dużych tablic, ale jest to jedyna wada tej prostej metody:

void sito(int n)

I

II    wypisuje wszystkie liczby pierwsze <n int *tp=new inttn+l);

for(int i-1;i<=n;i++) II zaznaczenie wszystkich tp[i]=i; II liczb naturalnych od 1 do n int cpt=l; while(cpt<n)

<

//szukamy pierwszego niezerowego elementu tablicy tp: for (cptt+; (tp[cpt]==0) && (cpt!=100); cptm ) ,-// zerujemy wielokrotności tego elementu (cpt) w tp int k=Z; while(cpt* k<=n) f

tp[cpt*k]-0; k++;

)