Dominik Matuszek

Jak już wcześniej wspominałem, w tym wpisie chciałbym zająć się optymalizacją kodu we wcześniejszym programie:

• Pętlę, sprawdzającą czy liczba jest pierwsza:
  

  for (j=1;j<i+1;j++){ if (i%j==0){ b++;}}

  Można zoptymalizować – ta pętla sprawdza dzielniki danej liczby, począwszy od liczby 1 do tej liczby. Można zredukować ją do pierwiastka z tej liczby, ponieważ jeśli przed nim nie pojawi się żaden dzielnik (poza 1), to za nim na pewno także nie może (poza daną nam liczbą). Wynika to z tego, liczba będąca dzielnikiem danej liczby i będąca większa niż jej pierwiastek po wykonaniu operacji dzielenia ze sprawdzaną liczbą da nam jej inny dzielnik , mniejszy niż pierwiastek ze sprawdzanej liczby.

• Możemy zupełnie zmienić metodę – Tworzymy tablicę liczb (np. od 1 do 1000000). Najmniejszą liczbą pierwszą  jest 2 , więc wszystkie jej wielokrotności ( poza nią samą) będą złożone. Usuwamy je zatem z tablicy. Idziemy do kolejnej liczby w tablicy. Od razu będziemy o niej wiedzieć, że jest pierwsza. Usuwamy zatem jej wszystkie wielokrotności (poza nią samą). W ten sposób szybko zmniejszamy liczbę liczb w tablicy. Metoda ta znana jest jako Sito Eratostenesa.

Kodu tego niestety nie można skompilować we własnym kompilatorze języka C++, ze względu na to, iż WordPress zmienił niestety pewne znaki w kodzie na inne. Po symbolu „//” oznaczającym komentarz, znajduje się informacja nt. działania programu.  W kolejnym wpisie chciałbym zająć się optymalizacją algorytmu w tym programie, gdyż algorytm który jest zawarty w kodzie poniżej, jest jednym z najprostszych, ale i mniej efektywnych.

#include <bits/stdc++.h>
 using namespace std;
 int main(){
 //kod główny
 int i=1;
 int j=i;
 int a;
 int b=0; //Definiujemy zmienne
 cout<<"Proszę mi podać, do jakiej liczby mają być wypisywane liczby pierwsze ";
 cin>>a; //Pobieramy wartość, do jakiej mają być wypisywane liczby pierwsze

for (i=0;i<a+1;i++){ //Pętla wypisująca liczby pierwsze
 b=0; // Zerujemy liczbę dzielników za każdym powtórzeniem pętli
 for (j=1;j<i+1;j++){ //Pętla sprawdzająca ile dzielników ma dana liczba
 if (i%j==0){ //Jeżeli reszta z dzielenia jest równa 0, dodajemy do zmiennej liczbę jeden
 b++;
 }
 }
 if (b==2){
 cout<<i; //Jeśli liczba ma 2 dzielniki, wypisujemy numer powtórzenia pętli (czyli analizowaną liczbę)
 cout<<" "; //Program po wypisaniu liczby pierwszej wypisze także odstęp
 }

}
 }

Jest to pierwszy wpis dotyczący programu podającego kolejne liczby pierwsze.  W tej części postaramy się wymyślić algorytm , który będzie nam je wypisywać.

Zanim zaczniemy, powiedzmy sobie co to iterator.

Iterator jest to wskaźnik, naliczający który raz została wykonana pętla.

Zatem zacznijmy.

1. START
2.  Pytamy użytkownika, do jakiej liczby chce mieć wypisane liczby pierwsze.
3. Tworzymy pętlę, działającą od liczby 2 ( najmniejszej liczby pierwszej) do liczby podanej przez użytkownika.
4. Generujemy liczbę równą iteratorowi.
5. Sprawdzamy , czy dana liczba to liczba pierwsza. Jeśli tak, wypisujemy ją.
6. Sprawdzamy, czy liczba podana przez użytkownika jest mniejsza niż iterator. Jeśli tak, przechodzimy do punktu 7. . Jeśli nie, wracamy do punktu  4.
7. KONIEC

W następnym wpisie chciałbym pokazać, jak to będzie wyglądać w języku C++. Od razu mogę jednak powiedzieć,  że część punktów ww. programu będzie scalona z innymi (np. pkt. 6 zostanie uwzględniony w punkcie 3. , a pkt. 5. trzeba będzie rozpisać).