Algoritam Eratostenovog sita: Python, C++ Primjer

Eratostenovo sito je najjednostavnije sito prostih brojeva. To je algoritam prostih brojeva za pretraživanje svih prostih brojeva u zadanoj granici. Postoji nekoliko sita prostih brojeva. Na primjer, Eratostenovo sito, Atkinovo sito, Sundaramovo sito itd.

Riječ "sito” znači posuđe koje filtrira tvari. Dakle, algoritam sita u Python i drugim jezicima odnosi se na algoritam za filtriranje prostih brojeva.

Ovaj algoritam filtrira primarni broj u iterativnom pristupu. Proces filtriranja počinje s najmanjim prostim brojem. Prosti je prirodni broj koji je veći od 1 i ima samo dva djelitelja, naime 1 i sam broj. Brojevi koji nisu prosti nazivaju se složeni brojevi.

U situ Eratostenove metode prvo se odabire mali prosti broj, a svi njegovi višekratnici se filtriraju. Proces se izvodi u petlji u zadanom rasponu.

Na primjer:

Uzmimo raspon brojeva od 2 do 10.

Algoritam Eratostenovog sita

Nakon primjene Eratostenovog sita, proizvest će popis prostih brojeva 2, 3, 5, 7

Algoritam Eratostenovog sita

Eratostenovo sito algoritma

Ovo je algoritam za Eratostenovo sito:

Korak 1) Napravite popis brojeva od 2 do zadanog raspona n. Počinjemo s 2 jer je to najmanji i prvi prosti broj.

Korak 2) Odaberite najmanji broj na popisu, x (u početku je x jednako 2), prođite kroz popis i filtrirajte odgovarajuće složene brojeve označavajući sve višekratnike odabranih brojeva.

Korak 3) Zatim odaberite sljedeći prosti ili najmanji neoznačeni broj na popisu i ponovite korak 2.

Korak 4) Ponavljajte prethodni korak sve dok vrijednost x ne bude manja ili jednaka kvadratnom korijenu iz n (x<=Eratostenovo sito algoritma).

Bilješka: Matematičko razmišljanje je vrlo jednostavno. Raspon brojeva n može se faktorizirati kao

n=a*b

Opet, n =Eratostenovo sito algoritma*Eratostenovo sito algoritma

= (faktor manji od Eratostenovo sito algoritma) * (faktor veći od Algoritam Eratostenovog sita)

Dakle, barem jedan od glavni faktori ili oba moraju biti <=Eratostenovo sito algoritma. Dakle, prelazeći na Eratostenovo sito algoritma bit će dovoljno.

Korak 5) Nakon ta četiri koraka, preostali neoznačeni brojevi bili bi svi prosti brojevi u danom rasponu n.

Primjer:

Uzmimo primjer i vidimo kako funkcionira.

Za ovaj primjer, pronaći ćemo popis prostih brojeva od 2 do 25. Dakle, n=25.

Korak 1) U prvom koraku uzet ćemo popis brojeva od 2 do 25 jer smo odabrali n=25.

Eratostenovo sito algoritma

Korak 2) Zatim odabiremo najmanji broj na listi, x. U početku x=2 jer je to najmanji prosti broj. Zatim prelazimo kroz popis i označavamo višekratnike 2.

Višekratnici broja 2 za danu vrijednost n su: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Algoritam Eratostenovog sita

Bilješka: Plava boja označava odabrani broj, a ružičasta boja označava eliminirane višekratnike

Korak 3) Zatim biramo sljedeći najmanji neoznačeni broj, a to je 3, i ponavljamo zadnji korak označavajući višekratnike broja 3.

Algoritam Eratostenovog sita

Korak 4) Ponavljamo korak 3 na isti način dok x=Algoritam Eratostenovog sita ili 5.

Algoritam Eratostenovog sita

Korak 5) Preostali neoznačeni brojevi bili bi prosti brojevi od 2 do 25.

Algoritam Eratostenovog sita

Pseudo-kod

Begin
	Declare a boolean array of size n and initialize it to true
	For all numbers i : from 2 to sqrt(n)
     		IF bool value of i is true THEN
         			i is prime
         			For all multiples of i (i<n)
             			mark multiples of i as composite
Print all unmarked numbers
End

Eratostenovo sito C/C++ primjer koda

#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
    // Create and initialize a boolean array
    bool primeNumber[n + 1];
    memset(primeNumber, true, sizeof(primeNumber));
    for (int j = 2; j * j <= n; j++) {
        if (primeNumber[j] == true) {
            // Update all multiples of i as false
            for (int k = j * j; k <= n; k += j)
                primeNumber[k] = false;
        }
    } 
    for (int i = 2; i <= n; i++)
        if (primeNumber[i])
            cout << i << " ";
}
int main()
{
    int n = 25;
    Sieve_Of_Eratosthenes(n);
    return 0;
} 

Izlaz:

2 3 5 7 11 13 17 19 23

Sita Eratostena Python Primjer programa

def SieveOfEratosthenes(n):
# Create a boolean array
	primeNumber = [True for i in range(n+2)]
	i = 2
	while (i * i <= n):
		if (primeNumber[i] == True):
			# Update all multiples of i as false
			for j in range(i * i, n+1, i):
				primeNumber[j] = False
		i += 1
	for i in range(2, n):
		if primeNumber[i]:
			print(i)
n = 25
SieveOfEratosthenes(n)

Izlaz:

2
3
5
7
11
13
17
19
23

Segmentirano sito

Vidjeli smo da je Eratostenovo sito potrebno za pokretanje petlje kroz čitav raspon brojeva. Stoga mu je potrebno O(n) memorijskog prostora za pohranjivanje brojeva. Situacija postaje komplicirana kada pokušavamo pronaći proste brojeve u velikom rasponu. Nije moguće dodijeliti tako velik memorijski prostor za veći n.

Algoritam se može optimizirati uvođenjem nekih novih značajki. Ideja je podijeliti raspon brojeva u manje segmente i izračunati proste brojeve u tim segmentima jedan po jedan. Ovo je učinkovit način smanjenja složenosti prostora. Ova metoda se naziva a segmentirano sito.

Optimizacija se može postići na sljedeći način:

  1. Pomoću jednostavnog sita pronađite proste brojeve od 2 do Segmentirano sito i pohraniti ih u niz.
  2. Podijelite raspon [0…n-1] u više segmenata najviše veličine Segmentirano sito
  3. Za svaki segment, iterirajte kroz segment i označite višekratnik prostih brojeva pronađenih u koraku 1. Ovaj korak zahtijeva O(Segmentirano sito) na maks.

Redovno sito zahtijeva O(n) pomoćnog memorijskog prostora, dok segmentirano sito zahtijeva O(Segmentirano sito), što je veliki napredak za veliki n. Metoda ima i lošu stranu jer ne poboljšava vremensku složenost.

Analiza složenosti

Složenost prostora:

Jednostavno sito Eratostenovog algoritma zahtijeva O(n) memorijskog prostora. I segmentirano sito zahtijeva
O(Analiza složenosti) pomoćni prostor.

Složenost vremena:

Vremenska složenost regularnog sita Eratostenovog algoritma je O(n*log(log(n))). Razlozi za ovu složenost razmatraju se u nastavku.

Za zadani broj n, vrijeme potrebno za označavanje složenog broja (tj. neprostih brojeva) je konstantno. Dakle, broj pokretanja petlje jednak je-

n/2 + n/3 + n/5 + n/7 + ……∞

= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)

Harmonijska progresija zbroja prostih brojeva može se oduzeti kao log(log(n)).

(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))

Dakle, vremenska složenost će biti-

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= n * log(log(n))

Dakle, vremenska složenost O(n * log(log(n)))

Zatim ćete naučiti o Pascalov trokut

rezime

  • Eratostenovo sito filtrira proste brojeve u zadanoj gornjoj granici.
  • Filtriranje prostog broja počinje od najmanjeg prostog broja, "2". Ovo se radi iterativno.
  • Iteracija se provodi do kvadratnog korijena iz n, gdje je n zadani raspon brojeva.
  • Nakon ovih ponavljanja, brojevi koji ostaju su prosti brojevi.