Sito Eratostenesa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Sito Eratostenesa
154 KB
Przykładowe działanie Sita Eratostenesa
Struktura danych Tablica, lista
Złożoność
Czasowa O((n log n)(log log n))
Pamięciowa O(n)

Sito Eratostenesa - przypisywany Eratostenesowi z Cyreny algorytm wyznaczania liczb pierwszych z zadanego przedziału [2,n]\;.

Algorytm[edytuj | edytuj kod]

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, bądź równe 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

Implementacja[edytuj | edytuj kod]

Go[edytuj | edytuj kod]

package main
 
import (
	"fmt"
	"bufio"
	"os"
	"strconv"
)
 
func main() {
 
	var czytaj *bufio.Scanner = bufio.NewScanner(os.Stdin)
	var zakres int;
 
	fmt.Println("Podaj liczbę do której szukać liczb pierwszych:")
	czytaj.Scan()
	zakres, _ = strconv.Atoi(czytaj.Text())
  	tablica := make([]bool, zakres + 1)
 
	for i:=2 ; i*i <= zakres ; i++ {
		if tablica[i] == true { continue }
		for j:=2*i ; j<=zakres ; j += i { tablica[j] = true }
	}
 
	fmt.Println("Liczby pierwsze z przedziału od 0 do", zakres, "to:")
	for i:=2 ; i <= zakres ; i++ { 
		if tablica[i] == false { fmt.Print(i, ", ") } 
	}
}

C++[edytuj | edytuj kod]

#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 liczba 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;
}

C#[edytuj | edytuj kod]

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();
        }
    }
}

Pascal[edytuj | edytuj kod]

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

Python[edytuj | edytuj kod]

#! /usr/bin/env python
# -*- coding: utf-8 -*-
 
# zakres poszukiwań
n = 150
 
# lista liczb od 2 do n (0 i 1 nie są liczbami pierwszymi)
numbers = range(2, n + 1)
 
# usuwanie wielokrotności liczb pierwszych
for prime in numbers:
    for multiple in range(2 * prime, n + 1, prime):
        if multiple in numbers:
            numbers.remove(multiple)
 
print("Liczby pierwsze z zakresu od 2 do {0}:".format(n))
print(numbers)

Java[edytuj | edytuj kod]

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);
 
    }
 
}

Asembler[edytuj | edytuj kod]

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

MATLAB[edytuj | edytuj kod]

function liczby_pierwsze=esito2(wektor)
%Sito Eratostenesa
zakres=2:floor(sqrt(max(wektor)));
liczby_pierwsze=wektor;
for i=1:length(zakres)
    liczby_pierwsze=liczby_pierwsze(mod(liczby_pierwsze,zakres(i))~=0 & liczby_pierwsze~=zakres(i));
end
end

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]