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.
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
def eratoszthenesz_szitaja(n):
# Kezdetben minden számot prímszámként jelölünk
prime =
p = 2
while p * p <= n:
if prime:
# Töröljük a p többszöröseit
for i in range(p * p, n + 1, p):
prime = False
p += 1
# Az összes prím visszaadása
primes = ]
return primes
# Példa
n = 50
print(f"A prímszámok {n}-ig:", eratoszthenesz_szitaja(n))
# Kimenet: A prímszámok 50-ig:
#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) {
// Töröljük a p többszöröseit
for (int i = p * p; i <= n; i += p) {
prime = false;
}
}
}
// Az összes prím összegyűjtése
for (int p = 2; p <= n; ++p) {
if (prime) {
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;
}
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ő.