Question

DOWÓD - ODNOŚNIE SITA ERATOSTENESA.

Chcemy sprawdzić, czy dana liczba n jest pierwsza. Korzystamy z sita Eratostenesa - czyli wykreślamy wielokrotności kolejnych liczb pierwszych od 2 do .

Pytanie: Dlaczego wystarczy sprawdzać tylko do , a nie do n czy jakiejś innej liczby? Prosiłbym o ogólne uzasadnienie (nie dla konkretnego n). Może być dowód słowny.

Answer 1

Aby zrozumieć, dlaczego tak się dzieje:
1. pomyśl, kiedy liczba nie jest pierwsza - wtedy, kiedy iloczynem jakichś liczb pierwszych.
2.Jak działa ten algorytm: bierze kolejne liczby pierwsze z sita, po czym sprawdza, czy któraś dzieli bez reszty tą liczbę n. Jeżeli tak, to n jest nie pierwsza. A teraz zwróć uwagę:
gdyby dana liczba niepierwsza n była iloczynem liczb pierwszych "a" i  "b", to jeżeli a i b >²√n, to a*b > n, co nie może być prawdą, w końcu iloczyn tych liczb ma być równy n. W takim razie ustaliliśmy, że conajmniej jedna z liczb pierwszych, których iloczynem jest liczba niepierwsza musi być mniejsza od ²√n. Teraz wystarczy sprawdzić podzielność n tylko do tej właśnie liczby, aby wiedzieć, czy n jest pierwsza.
Trochę pogmatwane, ale mam nadzieję, że zrozumiesz:)

Answer 2

Na czym polega sito tak?

Ze zbior [2; +oo) , ponieważ jak wiadomo 1 nie jest pierwsza wykreślamy wielokrotności liczby n.

Czyli dla 2 wykreslamy 4,6,8 itd...
dla 3 wykreslamy 9 (bo 6 juz jest wykreslone przez 2), 15, 21 itd
i tak samo dla 5 ...
Postępujemy tak do póki liczba 'm' której wielokrotność wykreslamy będzie wieksza niz pierw(n) i w tedy dla kazdej liczby 'n' wszystkie niewykreślone są liczbami pierwszymi :)

Ponieważ określa małą( mniejszą ) część badanego zbioru i daje nam dokładnie wyklarowany zbiór liczb które są pierwsze. Dlaczego algorytm jest poprawny, bo sprawdzasz wszystkie liczby po kolei, ale przy kazdym sprawdzeniu jest ich dużo mnie bo kolejne wielokrotności są skreślane