Wikiszótár

Eratoszthenész szitája

Magyar

Kiejtés

  • IPA: [ ˈɛrɒtosthɛneːsːitaːjɒ]

Főnév

Eratoszthenész szitája

  1. (matematika, algoritmusok) 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 Eratoszthenész szitája egy hatékony algoritmus, amely a prímszámok meghatározására szolgál egy adott számig ((n)). Az algoritmus alapelve, hogy a prímszámok többszöröseit lépésenként kizárja, így csak a prímszámok maradnak.


Elméleti működés

  1. Kezdeti lista:
    • Készítsünk egy listát (2)-tól (n)-ig terjedő számokkal.
    • Minden számot kezdetben prímszámnak feltételezünk.
  2. Többszörösök kizárása:
    • Kezdjük a (2)-es számmal (ez az első prímszám).
    • Töröljük a (2)-nél nagyobb többszöröseit a listából, mivel azok nem lehetnek prímek.
    • Lépjünk a következő számra, amely még a listán maradt, és ismételjük meg a folyamatot.
  3. Iteráció vége:
    • Addig folytatjuk a folyamatot, amíg el nem érjük ()-et. Az ennél nagyobb számok már csak akkor maradhatnak a listán, ha prímek.
  4. Eredmény:
    • Az algoritmus végén a listán maradt számok mind prímszámok.


Tulajdonságok

  • Időkomplexitás: (O(n (n))), mivel a többszörösök kizárása gyorsan halad.
  • Térkomplexitás: (O(n)), mivel egy méretű (n)-es tömböt használunk.
  • Egyszerű implementációval nagyon hatékony akár nagy számok esetén is.


Pszeudokód

EratosztheneszSzitaja(n):
    jelöld prímként az összes számot 2-tól n-ig
    ciklus p = 2-tól √n-ig:
        ha p prím:
            töröld p összes többszörösét a prímek közül
    visszatér az összes megmaradt prím

Python implementáció

def eratoszthenesz_szitaja(n):
    # Kezdetben minden számot prímszámként jelölünk
    prime = [True for _ in range(n + 1)]
    p = 2

    while p * p <= n:
        if prime[p]:
            # Töröljük a p többszöröseit
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1

    # Az összes prím visszaadása
    primes = [p for p in range(2, n + 1) if prime[p]]
    return primes

# Példa
n = 50
print(f"A prímszámok {n}-ig:", eratoszthenesz_szitaja(n))
# Kimenet: A prímszámok 50-ig: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

C++ implementáció

#include <iostream>
#include <vector>
using namespace std;

vector<int> eratoszthenesz_szitaja(int n) {
    // Kezdetben minden számot prímszámként jelölünk
    vector<bool> prime(n + 1, true);
    vector<int> primes;

    for (int p = 2; p * p <= n; ++p) {
        if (prime[p]) {
            // Töröljük a p többszöröseit
            for (int i = p * p; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }

    // Az összes prím összegyűjtése
    for (int p = 2; p <= n; ++p) {
        if (prime[p]) {
            primes.push_back(p);
        }
    }

    return primes;
}

int main() {
    int n = 50;
    vector<int> primes = eratoszthenesz_szitaja(n);

    cout << "A prímszámok " << n << "-ig: ";
    for (int prime : primes) {
        cout << prime << " ";
    }
    cout << endl;

    return 0;
}

Optimalizáció

  1. Kezdőpont:
    • A többszörösök kizárását (p^2)-től kezdjük, mivel a kisebb többszörösök már korábban kizárásra kerültek.
  2. Páros számok kihagyása:
    • Az algoritmust tovább gyorsíthatjuk azzal, hogy csak a páratlan számokat vizsgáljuk.
  3. Bit-manipuláció:
    • Memóriatakarékosság érdekében bitmezőket (bitset) használhatunk a prímek jelölésére.


Összegzés

Az Eratoszthenész szitája egyszerűsége és hatékonysága miatt az egyik legismertebb algoritmus a prímszámok meghatározására. Oktatási célokra is kiváló, mivel az alapötlet könnyen érthető, és nagyobb számok esetén is jól működik. Optimalizációkkal nagyon gyorssá tehető.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Eratoszthenész_szitája&oldid=3479449”