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 Implementacja w języku Pascal 4 Zobacz też 5 Linki 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; 
vector<bool> isPrime(SIZE+1,true); // tworzymy tablicę, której wszystkie liczby na początku są pierwsze
/*
        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 Eratostenesa */
void makeTable()
{
        int i,j;
        
        
        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] Implementacja w języku Pascal

program sito_eratostenesa;
uses crt;
var n,i,j:Integer;
var tab: array[1..100] of Boolean;
begin
   clrscr;
   Writeln('Podaj liczbe naturalna od 1 do 100');
   readln(n);
   for i:=1 to n do tab[i]:=TRUE;
   for i:=2 to (n+1) div 2 do
   if tab[i] then 
   for j:=2 to (n div i) do
     begin
      tab[i*j]:=FALSE;
     end;
   Writeln('Oto kolejne liczby pierwsze z przedzialu [1,',n,']');
   for i:=2 to n do
     begin
      if (tab[i]) then
      Write(i,',');
     end;
    readkey;
end.

[edytuj] Zobacz też

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

[edytuj] Linki zewnętrzne

• Animacja sita Eratostenesa