Algorytm liczb pierwszych w C++: Sito Eratostenesa

Liczby pierwsze od zawsze były przedmiotem fascynacji matematyków i informatyków. Algorytm liczb pierwszych „Sito Eratostenesa” to jedno z najstarszych i najbardziej efektywnych narzędzi służących do identyfikacji liczb pierwszych w danym zakresie. W artykule zgłębimy ten algorytm, a także zobaczymy, jak można go zaimplementować w języku C++.

Sito Eratostenesa – Szybkie Wykrywanie Liczb Pierwszych

Algorytm sito Eratostenesa został nazwany od imienia greckiego matematyka Eratostenesa z Cyreny, który żył w III wieku p.n.e. Chociaż jego dokładne dzieło nie zachowało się, to znane jest narzędzie, które stworzył do znajdowania liczb pierwszych. Algorytm ten jest prosty, ale jednocześnie bardzo efektywny. Teraz utworzymy program do generowania liczb pierwszych za pomocą sita Eratostenesa. Wykorzystamy do tego język programowania C++.

Zasada szukania liczb pierwszych jest następująca:

Tworzymy tablicę wartości logicznych indeksowaną od 2 do n, gdzie n jest limitem zakresu, dla jakiego będziemy szukać liczb pierwszych. Tablicę wypełniamy wartościami true. Kolejnym etapem jest usuwanie liczb, które nie są liczbami pierwszymi poprzez oznaczanie odpowiadających im pól tabeli jako false. Wykreślanie odbywa się w następujący sposób: dla liczb od 2 do k (gdzie k to zaokrąglony w dół do całości pierwiastek kwadratowy z liczby n – limitu) wykreślamy wielokrotności tej liczby z tablicy. Wypisanie liczb pierwszych ogranicza się do wypisania indeksów pól tabeli, których wartość to true.

Krok 1: Inicjalizacja

Na początku należy podać programowi zakres poszukiwań liczb pierwszych. Wartość ta jest przechowywana w zmiennej zakres. Następnie tworzona jest tablica boolowska o rozmiarze zakres + 1 (włącznie z 0 i zakres), gdzie każdy element początkowo ustawiany jest na true. Tablica ta będzie przechowywała informacje o tym, czy dana liczba jest pierwsza. Zaczniemy od indeksu 2, ponieważ liczby pierwsze zaczynają się od „2”. Definicja liczby pierwszej mówi, że jest to liczba naturalna większa od 1, która dzieli się tylko przez 1 i przez siebie samą.

bool *tablica = new bool[zakres + 1];

for (int i = 2; i <= zakres; i++)
	{
		tablica[i] = true;
	}

Krok 2: Eliminacja liczb niepierwszych

W tej części algorytmu, dla każdej liczby pierwszej i, wszystkie jej wielokrotności są oznaczane jako niepierwsze. W rezultacie, zostają jedynie liczby pierwsze. W pętli for można również użyć zapisu i<=limit zamiast i * i <= zakres, ale będzie to mniej wydajne, gdyż musielibyśmy obliczać pierwiastek za każdym razem.

for (int i = 2; i * i <= zakres; i++)
{
    if (tablica[i])
    {
        for (int j = i * i; j <= zakres; j += i)
        {
            tablica[j] = false;
        }
    }
}

Krok 3: Wyświetlanie Liczb Pierwszych

Na koniec, program wyświetla liczby pierwsze z zakresu od 1 do zakres, sprawdzając tablicę tablica i wypisując jedynie te liczby, dla których odpowiadające im elementy tablicy są oznaczone jako true.

std::cout << "Liczby pierwsze z zakresu od 1 do " << zakres << ":" << std::endl;
	for (int i = 2; i <= zakres; i++)
	{
		if (tablica[i])
		{
			std::cout << i << std::endl;
		}
	}

Podsumowanie

Algorytm sito Eratostenesa to jedno z najstarszych narzędzi matematycznych, które znalazło zastosowanie w programowaniu. Jego prostota sprawia, że jest to świetne narzędzie do efektywnego znajdowania liczb pierwszych w danym zakresie. Implementacja w języku C++ wykorzystuje tablicę boolowską do szybkiego oznaczania liczb pierwszych i eliminacji ich wielokrotności. Algorytm ten stanowi kluczowy element w badaniu struktury liczb pierwszych oraz w wielu praktycznych zastosowaniach informatycznych.

Opis całego algorytmu jest trochę zagmatwany, ale po jego przestudiowaniu wszystko powinno się rozjaśnić:

#include <iostream>

int main()
{
	int zakres;

	std::cout << "Jaki zakres mam przeszukać?" << std::endl;
	std::cin >> zakres;
	std::cout << std::endl;

	if (zakres < 2)
	{
		std::cout << "Brak liczb pierwszych w podanym zakresie." << std::endl;
		return 0;
	}

	bool *tablica = new bool[zakres + 1];

	for (int i = 2; i <= zakres; i++)
	{
		tablica[i] = true;
	}

	for (int i = 2; i * i <= zakres; i++)
	{
		if (tablica[i])
		{
			for (int j = i * i; j <= zakres; j += i)
			{
				tablica[j] = false;
			}
		}
	}

	std::cout << "Liczby pierwsze z zakresu od 1 do " << zakres << ":" << std::endl;
	for (int i = 2; i <= zakres; i++)
	{
		if (tablica[i])
		{
			std::cout << i << std::endl;
		}
	}

	delete[] tablica;

	return 0;
}