Eratostenana sivo

Algoritmo dil Eratostenana sivo.

Eratostenana sivo esas algoritmo di selektar omna prima nombri min granda kam determinita, do de 2 til n – $[2,n]$, e bazas yel elimino di kompozita nombri. Autoro di metodo esis Eratosteno di Kyrene.

Algoritmo

De ensamblo di nombri naturala de $[2,n],$ to esas $\{2,3,4,\dots ,n\},$ on selektas minim granda, do 2, ed on eliminas olua omna multipliki plu granda kam ol ipsa, to esas $4,6,8,\dots$

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

De cetera nombri on selektas minim granda ankor ne eliminita (3) ed on eliminas olua omna multipliki plu granda kam ol ipsa: $6,9,12,\dots ,$ che duopl elimino es nula problemo (ex. nombri 6 o 12).

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

Segun la sama proceduro on kondutas por nombro 5.

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

Pose por nombro 7 til kontrolar omna ne eliminita nombri plu frue.

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

Elimino on repetas til nombro $i$, olquan multipliko ni eliminas, esos plu granda kam $\sqrt{n}$.

Pod determinita nombro $n$ omna ne eliminita nombri min granda od equala $n$ es prima nombri.

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60