Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

liczby pierwsze

Ostatnio zmodyfikowano 2019-10-18 07:50
Autor Wiadomość
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;
}
P-175388
jankowalski25
» 2019-10-17 20:10:52
Sito Eratostenesa

Dopisano:
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.
P-175390
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
P-175391
« 1 »
  Strona 1 z 1