Liczby pierwsze - jak działa ten program?

0

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 ii 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 ii=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;
}
0

Ten program jest realizacją sita Eratostenesa.

1

To nie jest Sito Erastotenesa, ten program, bardzo naiwnie sprawdza czy liczba wczytana jest pierwsza. W pętli do pierwiastka kwadratowego z n włącznie, szuka tegoż n dzielników, jeśli nie znajdzie, to pierwsza = false i drukuje "Nie", a "Tak" w przeciwnym przypadku.

EDIT: Jeszcze odpowiedź na Twoje pytanie o liczbę siedem. I wystarczy gdyż pierwiastek z siedmiu jest mniejszy od trzech, a dzielnik, (właściwy i nie jedynka) o ile istnieje jest mniejszy lub równy pierwiatkowi z liczby.
https://pl.wikipedia.org/wiki/Test_pierwszo%C5%9Bci

1
micw napisał(a):

W tytule: Liczby pierwsze - jak działa ten program?

Raczej powinieneś pytać jak ten program nie działa.
https://ideone.com/JdQ1rB

1 użytkowników online, w tym zalogowanych: 0, gości: 1