Eratoszthenész szitája

A Wikipédiából, a szabad enciklopédiából
Eratoszthenész szitája

Eratoszthenész szitája a neves ókori görög matematikus, Eratoszthenész módszere, melynek segítségével egyszerű kizárásos algoritmussal megállapíthatjuk, hogy melyek a prímszámok – papíron például a legkönnyebben 1 és 100 között.

Az algoritmus[szerkesztés]

1. Írjuk fel a számokat egymás alá 2-től ameddig a prímtesztet elvégezni kívánjuk. Ez lesz az A lista. (Az animáció bal oldalán.)
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2. Kezdjünk egy B listát 2-vel, az első prím számmal. (Az animáció jobb oldalán.)
3. Húzzuk le 2-t és az összes többszörösét az A listáról.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
4. Az első át nem húzott szám az A listán a következő prím. Írjuk fel a B listára.
5. Húzzuk át az így megtalált következő prímet és az összes többszörösét.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
6. Ismételjük a 3–5. lépéseket, amíg az A listán nincs minden szám áthúzva.

A pszeudokód[szerkesztés]

Az algoritmus pszeudokódja:

 // legfeljebb ekkora számig megyünk el
 utolso ← 100

 // abból indulunk ki, hogy minden szám prímszám
 ez_prim(i) ← igaz, i ∈ [2, utolso]

 for n in [2, √utolso]:
     if ez_prim(n):
         // minden prím többszörösét kihagyjuk,
         // a négyzetétől kezdve
         ez_prim(i) ← hamis, i ∈ {n², n²+n, n²+2n, …, utolso}

 for n in [2, utolso]:
     if ez_prim(n): nyomtat n

Programkód C#-ban[szerkesztés]

 1             Console.WriteLine("Kérem N értékét: ");
 2             string s = Console.ReadLine();
 3             int n = Convert.ToInt32(s);
 4             bool[] nums = new bool[n];
 5 
 6             nums[0] = false;
 7 
 8             for (int i = 1; i < nums.Length; i++)
 9             {
10                 nums[i] = true;
11             }
12 
13             int p = 2;
14 
15             while (Math.Pow(p, 2) < n)
16             {
17                 if (nums[p])
18                 {
19                     int j = (int) Math.Pow(p, 2);
20 
21                     while (j < n)
22                     {
23                         nums[j] = false;
24                         j = j + p;
25                     }
26                 }
27 
28                 p++;
29             }
30 
31             for (int i = 0; i < nums.Length; i++)
32             {
33                 if (nums[i])
34                 {
35                     Console.Write($"{i} ");
36                 }
37             }
38 
39             Console.ReadLine();

Programkód C++-ban[szerkesztés]

Optimális C++ kód, fájlba írással

//Az első M (itt 50) szám közül válogassuk ki a prímeket, fájlba írja az eredményt - Eratoszthenész Szitája
#include <iostream>
#include <fstream>
#include <string>

using namespace std;
int main()
{
	ofstream fout;
	string nev;
	cout << "Nev: "; cin >> nev; //fájlnév bekérése
	fout.open(nev.c_str());      //fájl létrehozása

	const int M = 50; //Meddig vizsgáljuk a számokat
	fout << "A(z) " << M << "-nel nem nagyobb primszamok:\n"; //A fájl bevezető szövege
	bool tomb[M + 1]; //logikai tömböt hozunk létre
	tomb[0] = tomb[1] = false; // a 0-át és az 1-et alapból hamisnak vesszük, hiszen nem prímek.
	for (int i = 2; i <= M; ++i) tomb[i] = true; //2-től indítjuk a for-t, alapból mindent igazra állítunk.
	for (int i = 2; i*i <= M; i++) {
		if (tomb[i]) {
			// prímet találtunk, a többszöröseit kiszitáljuk
			for (int j = i*i; j <= M; j += i) tomb[j] = false;
		}
	}

	for (int i = 0; i <= M; ++i) {
		if (tomb[i]) { //megnézzük hogy igaz-e
			fout << i << " "; // kiírja a fájlba a számokat, szóközzel elválasztva
		}
	}
}

Programkód Pascalban[1][szerkesztés]

program Eratoszthenesz_szitaja; 

{$APPTYPE CONSOLE}

uses SysUtils;

var n, i, j, p:longint;
  a: array of boolean;
begin
  Write('Kérem N értékét: ');
  ReadLn(n);
  SetLength(a, n + 1);
  a[1] := False;
  for i := 2 to n do a[i] := True;
  p := 2;
  while p * p <= n do
  begin
    if a[p] then
    begin
      j := p * p;
      while j <= n do
      begin
        a[j] := False;
        Inc(j, p);
      end;
    end;
    Inc(p);
  end;
  for i := 1 to n do if a[i] then Write(i, ' ');
  SetLength(a, 0);
  ReadLn;
end.

Programkód Pythonban[szerkesztés]

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from math import sqrt

n = 1000
lst = [True]*n                      # létrehozunk egy listát, ebben a példában 1000 elemmel
for i in range(2,int(sqrt(n))):     # A lista bejárása a 2 indexértéktől kezdve a korlát gyökéig
    for j in range(i*i, n, i):      # a listának azon elemeihez, melyek indexe az i-nek többszörösei, hamis értéket rendelünk
        lst[j] = False
for i in range(2,n):                # Kiíratjuk azoknak az elemeknek az indexét, melyek értéke igaz maradt
    if lst[i]:
        print i,

Források[szerkesztés]

Κόσκινον Ἐρατοσθένους or The Sieve of Eratosthenes (Being an Account of His Method of Finding All the Prime Numbers), Rev. Samuel Horsley, F. R. S. = Philosophical Transactions (1683–1775), 62(1772), 327–347.

További információk[szerkesztés]

  1. Simkó Lajos: Simkó Lajos gyakorikérdések válaszok - Eratoszthenész szitája. (Hozzáférés: 2016. február 26.)