Algorytm Sito Eratostenesa

[Calfy]

Witam,

mam stworzyć schemat blokowy algorytmu wykorzystującego sito Eratostenesa do znajdowania liczb pierwszych w danym przedziale. Z tym sobie poradzę. Chodzi mi o to, że nauczyciel powiedział, że przy zakresie \(\displaystyle{ <2;n>}\) wystarczy sprawdzać kolejne dzielniki do \(\displaystyle{ \sqrt{n}}\) i wszystkie liczby złożone zostaną wykreślone. Dlaczego tak jest?

[Dakurels]

Jeśli liczba ma jakieś dzielniki to ma dzielnik, który jest mniejszy od pierwiastka z tej liczby. Dlatego starczy skreślać tylko do pierwiastka.

[kadiii]

To jeszcze na pewno warto pokazać, prosty dowód:
jesli liczba złozona \(\displaystyle{ n=p \cdot q}\) miałaby same pierwiastki większe od \(\displaystyle{ \sqrt{n}}\) to
\(\displaystyle{ p> \sqrt{n}}\) i \(\displaystyle{ q> \sqrt{n}}\)

\(\displaystyle{ p \cdot q > \sqrt{n} \cdot \sqrt{n}=n}\) <-Sprzeczność