Sito Eratostenesa

Z RNO-Wiki
Wersja Rno (dyskusja | edycje) z dnia 07:31, 1 gru 2007
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)

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]


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ą */
			}
		}
	}
}


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 pamietamy 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)

Osobiste