Sito Eratostenesa

Sito Eratostenesa to algorytm wyznaczania liczb pierwszych z zadanego przedziału $[2,n]\;$.

Ze zbioru liczb naturalnych z przedziału $[2,n]\;$, tj. $\{2, 3, 4, \dots, n\},$ wybieramy najmniejszą, czyli 2 i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest $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

Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę (3) i usuwamy wszystkie jej wielokrotności większe od niej samej: $6, 9, 12, \dots$, 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

Wykreślanie powtarzamy do momentu, gdy liczba $i\;$, której wielokrotność wykreślamy, będzie większa niż $\sqrt{n}$.

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

Zapis algorytmu

Zapis algorytmu w języku C++:

#include <iostream>
 
using namespace std;
 
const int n = 100;
 
bool numbersTable[n + 1]; // tablica o indeksach od 0 do 100 | wszystkie false (czyli: 0);
 
int main()
{
    for (int i = 2; i*i <= n; i++ ) // przeszukuj liczby od 2 do sqrt(n), 0 i 1 nie są liczbami pierwszymi
    {
        if (numbersTable[i] == true) // jeżeli dana liczb jest już wykreślona
            continue; // to przejdź do kolejnej
        for (int j = 2 * i ; j <= n; j += i) // przejdź od liczby 2 * i do n przesuwając się o i
            numbersTable[j] = true; // i każdą z nich usuwaj ze zbioru
    }
 
    cout << "Liczby pierwsze z przedziału od 2 do " << n << ":" << endl;
 
    for (int i = 2; i <= n; i++) // przeszukaj liczby od 2 do n
        if (numbersTable[i] == false) // jeśli liczba nie została usunięta ze zbioru
            cout << i << endl; // to ją wypisz
    return 0;
}

Zapis algorytmu w języku Pascal:

program sito eratostenesa
var
tablica : array[1..100] of boolean;
i, b, c : integer;
n : int64;
 
begin
  n := 100;
  for i := 1 to n do tablica[i] := false;
 
  i := 1;
  repeat
    i := i + 1;
    b := 2 * i;
      repeat
        tablica[b] := true;
        b := b + i;
      until (b > n);
  until i > sqrt(n);
  for i := 1 to n do
  begin
    if (not tablica[i]) then
    write(i, ' ');
  end;
end.

Zapis algorytmu w języku JAVA:

public class Main 
{
    public static void main(String[] args)
    {
        int n = 100;
        boolean[] numbersTable = new boolean[n+1];
        for(int i = 2; i*i <= n; i++)
        {
            if (numbersTable[i] == true)
                continue;
            for (int j = 2 * i ; j <= n; j += i)
                numbersTable[j] = true;
 
        }
        System.out.println("Liczby pierwsze z przedziału od 2 do " + n + ":");
        for (int i = 2; i <= n; i++)
            if (numbersTable[i] == false)
                System.out.println(i);
 
    }
 
}

Zapis algorytmu w języku C#:

namespace ConsoleApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 0;
            Console.Write("Podaj liczbe: ");
            n = Convert.ToInt32(Console.ReadLine());
            bool[] tab = new bool[n+1];
            for (int i = 2; i * i <= n; i++)
            {
                if (tab[i] == true)
                {
                    continue;
                }
                for (int j = 2 * i; j <= n; j += i)
                {
                    tab[j] = true;
                }
            }
            Console.WriteLine("Liczby pierwsze z zakresu [0," + n + "]: ");
            for (int i = 2; i <= n; i++)
            {
                if (tab[i] == false)
                {
                    Console.Write(i + " ");
                }
            }
            Console.ReadKey();
        }
    }
}

Zapis w asemblerze:

segment .data 
limit   dd     2000000
segment        .text
        global _start
_start:        
        push   ebp
        mov    ebp,esp
 
        mov    ecx,[limit]
L1:
        push   ecx
        dec    ecx
        cmp    ecx,1
        jne    L1
 
        mov    ebx,4
L2:
        mov    edi,esp
        pop    ecx    
        cmp    ecx,0
        je     notPrime
 
        mov    eax,ecx
        call   _printEAXdecimal
 
        mov    eax,ecx
        xor    ecx,ecx
        mul    ebx
L3:
        mov    [edi],ecx
        add    edi,eax
        cmp    edi,ebp
        jg     notPrime
        jmp    L3
 
notPrime:
        cmp    ebp,esp
        jne    L2
 
        pop    ebp
 
        mov    eax,1        ; exiting
        mov    ebx,5
        int    0x80

Zobacz też

• sito Atkina
• Eratostenes

Linki zewnętrzne

• Animacja sita Eratostenesa
• implemetacja sita Eratostenesa w języku java