6837093811

//liczby pierwsze to zapisujemy ja na tablicy //i zwiększamy zmienną nilliczb; zmienna //illiczb (liczba dzielników) nie zmienia się

17.    }

18.    }

19.

20.

21.

for(int i=l; i<=nilliczb; i++){

printf("%i) %i\n",i,liczp[i]);//po skończeniu przesiewu //zawartość tablicy

wyświetlamy

)

22.    getchar();

23.    )

Liczby pierwsze zapisywane są na tablicy liczp. W liniach 7-12 wpisujemy na wspomnianą tablicę liczby spełniające warunek p²<=N (dla N=100) oraz określamy ilość liczb zgromadzonych na tablicy przy pomocy zmiennej illiczb, a także przypisujemy tą wartość zmiennej nilliczb, która będzie zliczała ilość liczb pierwszych w czasie ich odnajdywania. Linia 14 odpowiada za sprawdzanie liczby pod względem podzielności przez, umieszczone w liniach 7-12, liczby na tablicy. Zakres sprawdzanych liczb określamy pętlą for w linii 13. Na koniec (linie 19-21) wypisujemy zgromadzone na tablicy liczby.

Optymalizacja kodu - wstęp do przeszukiwania kolejnych zakresów

Zmodyfikujmy powyższy kod tak, aby mógł służyć do sprawdzania liczb większych od 100 na podstawie wyników wcześniejszych zakresów.

Zacznijmy od linii 14. Dla N=100 mamy tylko cztery dzielniki, więc możemy pozwolić sobie na wypisanie każdego warunku oddzielnie. Ilość dzielników wzrasta jednak po sprawdzeniu każdego kolejnego zakresu. Musimy więc zmodyfikować ten fragment. Dzięki zmiennym illiczb i nilliczb wiemy ile jest liczb na tablicy. Możemy zastosować pętle for dla dzielenia przez kolejne liczby pierwsze. Spowoduje to jednak, że wykonywane będzie dzielenie zawsze tyle razy ile liczb mamy na tablicy, pomimo tego, że sprawdzana liczba okaże się podzielna przez którąś z nich. Jeśli dzielenie przez 3 lub 5 da resztę 0 to dalsze dzielenie nie jest uzasadnione. Zastosujmy więc pętle while. Dodajmy zmienną flaga która będzie regulowała działanie pętli. Określmy, że pętla będzie wykonywana gdy flaga !=o. Wartość 0 należy w tej sytuacji przypisać zmiennej flaga, gdy: w wyniku dzielenia otrzymamy resztę 0;

wykonamy dzielenie tyle razy, ile liczb mieliśmy na tablicy przed rozpoczęciem przesiewu;

Aby umożliwić sprawdzanie drugiego z powyższych warunków wprowadźmy zmienną j, która będzie zliczała wykonania pętli. Sprawdzana liczba będzie pierwsza, jeśli wykonamy pętle tyle razy ile mamy na tablicy liczb i nie otrzymamy reszty 0 w ostatnim dzieleniu. Wprowadźmy zmienną fiagapoz, której zadaniem będzie zliczanie powtórzeń pętli, w których osiągnęliśmy resztę inną niż 0. Ostatecznie otrzymujemy:

--------------ŹRÓDŁO 2--------------

1.    flaga=l;//zmienna warunkująca wykonywanie pętli while

2.    flagapoz=0;//zmienna zliczająca ilość dzieleń z resztą inną niż 0

3.    j=0;//licznik wykonania pętli while

4.    while(flaga!=0)

5.    {

6.    j++;

7.    if(j>illiczb || liczba%liczp[j]==0){

8.    flaga=0;//jeśli wykonaliśmy dzielenie dla wszystkich liczb pierwszych

2