liczby pierwsze
Ostatnio zmodyfikowano 2019-10-18 07:50
micw Temat założony przez niniejszego użytkownika |
liczby pierwsze » 2019-10-17 19:17:37 Cześć, potrzebuje łopatologicznego wytłumaczenia poniższego programu, a konkretnie tego co dzieje się w pętli for. Nie rozumiem dlaczego pętla wykonuje się akurat do spełnienia warunku i*i oraz na jakiej zasadzie działa sprawdzanie czy liczba jest pierwsza. No bo załozmy ze wpisalem do sprawdzenia 7 wiec petla for sprawdza czy 7 dzieli sie bez reszty przez 2 a po tym petla sie konczy bo i*i=9 jest wieksze niz 7. Z tego wiemy ze nasza liczba n nie jest podzielna bez reszty przez 2 ale skad wiemy ze jest liczba pierwsza? #include <iostream> #include <cstdio> using namespace std;
int main() { int n; while (scanf_s("%d", &n)) { if (n == 1) break; bool pierwsza = true; for (int i = 2; i * i <= n; i++) if (n % i == 0) pierwsza = false; if (pierwsza) printf("Tak\n"); else printf("Nie\n");
}
return 0; } |
|
jankowalski25 |
» 2019-10-17 20:10:52 Sito EratostenesaDopisano:dlaczego pętla wykonuje się akurat do spełnienia warunku i*i |
Może się wykonywać dłużej, ale nie ma takiej potrzeby, bo po sprawdzeniu liczb aż do pierwiastka z n włącznie już wiadomo, czy liczba jest pierwsza, czy też nie. Wynika to z przemienności mnożenia. Jeśli sprawdzasz liczbę 26 i stwierdzisz, że dzieli się przez 2, to nie trzeba dalej sprawdzać, czy dzieli się jeszcze przez 13. na jakiej zasadzie działa sprawdzanie czy liczba jest pierwsza |
Masz ciąg liczb całkowitych od dwóch do nieskończoności. Wywalasz same parzyste (większe od dwójki). Aż do czwórki masz same liczby pierwsze. Wywalasz same liczby podzielne przez 3 (większe od trójki). Aż do dziewiątki masz same liczby pierwsze. I tak dalej, aż uzyskasz liczby pierwsze z takiego zakresu, z jakiego potrzebujesz. Po prostu przy wywalaniu kolejnych liczb dopiero od kwadratu danej liczby pierwszej pojawiają się nowe liczby do wyrzucenia, bo poprzednie zostały już odrzucone wcześniej. |
|
darko202 |
» 2019-10-18 07:50:03 dobrym narzędziem jest debuger. (google +"c++ debugger tutorial") Użyty pokazuje w dowolnym momencie przebieg algorytmu i stan zmiennych po każdej operacji. ułatwi Ci to życie :)
Powodzenia |
|
« 1 » |