Sito Eratostenesa

Z Wikipedii

Sito Eratostenesa to algorytm kolejnego wybierania liczb pierwszych z ciągu liczb naturalnych.

Ze zbioru liczb naturalnych większych od jedności, tj. {2, 3, 4, ...}, wybieramy najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest 4, 6, 8, ...

	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

Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę (3) i usuwamy wszystkie jej wielokrotności większe od niej samej: 6, 9, 12, ..., przy czym nie przejmujemy się tym, że niektóre liczby (na przykład 6 czy 12) będą skreślane więcej niż raz.

	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

Według tej samej procedury postępujemy dla liczby 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

Następnie dla 7, 11, 13; aż do sprawdzenia wszystkich niewykreślonych wcześniej liczb.

	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

Dla danej liczby n wszystkie niewykreślone liczby mniejsze od n są liczbami pierwszymi.

	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

Spis treści 1 Animacja 2 Implementacja w języku C++ 3 Zobacz też 4 Materiały zewnętrzne

[edytuj] Animacja

Poniższa animacja w poglądowy sposób przedstawia opisaną procedurę (niem. Primzahlen: liczby pierwsze):

[edytuj] Implementacja w języku C++

const int SIZE=1000000; // rozmiar tablicy
vector<bool> isPrime(SIZE+1);
/*
        isPrime
        {  cel :             / false , gdy n jest liczbą złożoną
                isPrime[n] = |
                             \ true  , gdy n jest liczbą pierwszą }
*/

/* Procedura obliczająca tablicę isPrime za pomocą metody sita Erastotenesa */
void makeTable()
{
        int i,j;
        for (i=2; i<=SIZE; i++)
                isPrime[i] = true; /* na początku wszystkie liczby są pierwsze */
        
        for (i=2; i*i<=SIZE; i++)
        {
                if (isPrime[i])
                {
                        for (j=i*i; j<=SIZE; j=j+i) // zaczynamy wykreślać od 'i'-tej wielokrotności liczby 'i'
                        {
                                isPrime[j] = false; /*  j - jest wielokrotnością liczby i,
                                                            a więc na pewno nie jest liczbą pierwszą */
                        }
                }
        }
}

[edytuj] Zobacz też

• Eratostenes,
• przegląd zagadnień z zakresu matematyki.

[edytuj] Materiały zewnętrzne

• Animacja sita Eratostenesa