Liczby pierwsze - jak działa ten program?

Liczby pierwsze - jak działa ten program?
MI
  • Rejestracja:ponad 5 lat
  • Ostatnio:około 5 lat
  • Postów:44
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?

Kopiuj
#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;
}
edytowany 5x, ostatnio: cerrato
Patryk27
Moderator
  • Rejestracja:ponad 17 lat
  • Ostatnio:ponad rok
  • Lokalizacja:Wrocław
  • Postów:13042
0

Ten program jest realizacją sita Eratostenesa.


edytowany 2x, ostatnio: Patryk27
Shalom
raczej trial division ;)
Patryk27
wowo, wtopa :D
_13th_Dragon
@Patryk27 nie zarywaj nocy, nie będzie wtop.
lion137
  • Rejestracja:około 8 lat
  • Ostatnio:2 minuty
  • Postów:4930
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


edytowany 4x, ostatnio: lion137
Zobacz pozostałe 7 komentarzy
_13th_Dragon
Popieram zdanie od @vpiotr oraz wg mnie dla liczb pojęcie poniżej nie jest stricte poprawne.
lion137
Zedytowałem post.
_13th_Dragon
No to wracamy do pierwszej uwagi, liczba 39 ma dzielnik 19, jest powyżej pierwiastka, czyli nadal nieścisła definicja.
lion137
Ścisła, dzielnik musi istnieć poniżej pierwiastka i 38 też taki posiada: 2.
_13th_Dragon
Ale napisałeś: ... dzielnik ... o ile istnieje ... no, istnieje - 19 ... jest mniejszy lub równy pierwia(s)tkowi z liczby no, jest zdecydowanie większy, rozumiesz nieścisłość?
_13th_Dragon
  • Rejestracja:ponad 19 lat
  • Ostatnio:dzień
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


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 1x, ostatnio: _13th_Dragon
lion137
:D Piękny "corner case"
_13th_Dragon
Jestem złośliwy ;P

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.