Sito Eratostenesa to klasyczny algorytm służący do wyznaczania liczb pierwszych mniejszych od danej liczby naturalnej. Polega na systematycznym wykreślaniu wielokrotności kolejnych liczb, zaczynając od 2, dzięki czemu pozostają tylko liczby pierwsze. Algorytm jest prosty w implementacji i bardzo wydajny — jego złożoność czasowa wynosi około $O(n\log \log n)$. Mimo że powstał w starożytności, do dziś znajduje zastosowanie w informatyce i matematyce.

W kryptografii liczby pierwsze odgrywają kluczową rolę, zwłaszcza w algorytmach opartych na teorii liczb, takich jak RSA. Sito Eratostenesa jest wykorzystywane do szybkiego generowania list małych liczb pierwszych, które służą m.in. do wstępnego testowania pierwszości dużych liczb. Dzięki temu można szybko odrzucić liczby złożone, zanim zastosuje się bardziej zaawansowane testy pierwszości.

Ćwiczenia na rozgrzewkę: