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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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[i] = 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 Pascal-ban[szerkesztés | forrásszöveg szerkesztése]

const n = 2000000; {az n lehet bármilyen érték ami belefér longint-ba}
var n,i,j,p:longint;
    a:array[1..n] of boolean; {logikai tömböt hozunk létre}
    fout:text; {kimeneti fájl}
Begin
  assign(fout,'Név'); rewrite(fout);
  a[1]:=false; {az a[1] hamisat vesz fel mivel az 1 nem prímszám}
  for i:=2 to n do  {feltöltjük a tömböt igaz értékekkel}
    a[i]:=true;
  p:=2;
  while p*p <= n do begin
    if a[p] then begin
      {prímet találtunk, a többszöröseit kiszitáljuk}
      j:=p*p;
      while j <= n do begin
        a[j]:=false;
        j:=j+p;
      end;
    end;
  end;
  for i:=1 to n do   {kiíratjuk azokat az elemeket amelyek igazak maradtak, vagyis prímszámok}
    if a[i] then
      write(fout,i,' ');
close(fout);
End.

Programkód Python-ban.[szerkesztés | forrásszöveg szerkesztése]

#!/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 | forrásszöveg szerkesztése]

Κόσκινον Ἐρατοσθένους 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 | forrásszöveg szerkesztése]