Sito Eratostenesa

RNO-Wiki

Sito Eratostenesa służy do znajdowania liczb pierwszych w pewnym przedziale.

U nas będzie to przedział [1,SIZE], gdzie SIZE=1000000. Algorytm sita całkiem nieźle opisany jest w Polskiej Wikipedii, czyli tutaj [1].

Spis treści

Zobacz co piszą w Wikipedii

  • polska strona [2]
  • angielska [3]

Google

Implementacja w C/C++

const int SIZE=1000000; // rozmiar tablicy
vector<bool> isPrime(SIZE+1);
/*
	isPrime
	{  cel :             / false , gdy n jest liczbą złożoną
		isPrime[n] = |
		             \ true  , gdy n jest liczbą pierwszą }
*/
 
/* Procedura obliczająca tablicę isPrime za pomocą metody sita Eratostenesa */
void makeTable()
{
	int i,j;
	for (i=2; i<=SIZE; i++)
		isPrime[i] = true; /* na początku wszystkie liczby są pierwsze */
 
	for (i=2; i*i<=SIZE; i++)
	{
		if (isPrime[i])
		{
			for (j=i*i; j<=SIZE; j=j+i) // zaczynamy wykreślać od 'i'-tej wielokrotności liczby 'i'
			{
				isPrime[j] = false; /*  j - jest wielokrotnością liczby i,
							    a więc na pewno nie jest liczbą pierwszą */
			}
		}
	}
}

Konstrukcja tablicy kolejnych liczb pierwszych

Za pomocą tablicy isPrime można w łatwy sposób skonstruować tablicę kolejnych liczb pierwszych ithPrime[...] (indeksowaną od zera): 

vector<int> ithPrime(78498); // ithPrime[0]=2, ithPrime[1]=3, ..., ithPrime[78497]=999983
                             // ^--- liczby pierwsze nie większe niż 10^6
 
void make_ithPrime()
{
   int i=0;
   for(int p = 2; p <= SIZE; p++)
     if (isPrime[p]) ithPrime[i++] = p;
}

Uwaga: zamiast martwić się o rozmiar tablicy ithPrime możemy użyć super metody wektora - metody push_back: 

vector<int> ithPrime;
 
void make_ithPrime()
{
   for(int p = 2; p <= SIZE; p++) if (isPrime[p]) ithPrime.push_back(p);
}

Znajdowanie najmniejszego dzielnika pierwszego danej liczby

Za pomocą sita Eratostenesa można skonstruować tablicę fDiv, dla której 

 fDiv[n] = najmniejszy dzielnik pierwszy liczby n

Oto implementacja: 

const int SIZE=1000000; // rozmiar tablicy
vector<int> fDiv(SIZE+1);
/*
	fDiv - cel
	{  fDiv[n] = najmniejszy dzielnik pierwszy liczby n  }
*/
 
/* Procedura obliczająca tablicę fDiv za pomocą metody sita Eratostenesa */
void makeTable()
{
	int i,j;
	for (i=2; i<=SIZE; i++)
		fDiv[i] = i; /* na początku wszystkie liczby są pierwsze */
 
	for (i=2; i*i<=SIZE; i++)
	{
		if (fDiv[i]==i)
		{
			for (j=i*i; j<=SIZE; j=j+i) // zaczynamy wykreślać od 'i'-tej wielokrotności liczby 'i'
			{
				if ( fDiv[j]==j )   // jeśli sito uważa, że j jest liczbą pierwszą, to trzeba to zmienić
					fDiv[j]=i;  /*  j - jest wielokrotnością liczby i,
							    a więc na pewno nie jest liczbą pierwszą */
			}
		}
	}
}


Wnioski: tablica fDiv jest znacznie fajniejsza niż isPrime, bo pamiętamy w niej ciekawsze informacje.

Pierwszość liczby n>1 można sprawdzić w nastepujący sposób: 

// funkcja sprawdzająca pierwszość liczby n, za pomocą tablicy fDiv[...]
bool isPrime(int n) { return (n>1) ? fDiv[n]==n : false; } // uwaga (na n=1 i n=0)

Faktoryzacja

Za pomocą tablicy fDiv można szybko faktoryzować liczby z przedziału [1,SIZE*SIZE]. Jako ćwiczenie napisz funkcję, która dla danej liczby n>1, np. n=105 wypisze jej rozkład na czynniki pierwsze, np. w postaci 

 135=3*5*7


Rafał Nowak 08:31, 1 gru 2007 (CET)

Źródło: "http://www.rafalnowak.pl/wiki/index.php?title=Sito_Eratostenesa"
Widok
Osobiste
Nawigacja
Narzędzia