Perché basta fermarsi alla radice di N

Perché nel crivello ci si può fermare quando $p^2>N$? La ragione è semplice e riguarda ogni numero composto.

Osservazione — Perché basta fermarsi a $\sqrt{N}$

Se $n\le N$ fosse composto, allora $n=a\cdot b$ con $1<a\le b$. Ne segue $a\le\sqrt{n}\le\sqrt{N}$: il fattore più piccolo è $\le\sqrt{N}$. Dunque ogni numero composto $\le N$ ha un fattore primo $\le\sqrt{N}$ ed è già stato cancellato quando si sono eliminati i multipli dei primi fino a $\sqrt{N}$. Il costo del crivello è $O(N\log\log N)$: per $N=10^6$ bastano pochi millisecondi.

Collegamenti

Argomenti: Numeri e operazioni
Concetti: Crivello di eratostene · Numero primo
Competenze: Dimostrare