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.
