ERATOSTENOVO SITO
Eratostenovo sito je algoritam koji pomaže brzom rešavanju sledećeg problema:
Za dati prirodan broj n odrediti sve proste brojeve na segmentu od [1,n].
Ovaj problem se može rešiti prolaskom kroz petlju redom od 1-n i proverom svakog broja da li je prost pomoću funkcije koja određuje da li je poslati broj prost:
Za dati prirodan broj n odrediti sve proste brojeve na segmentu od [1,n].
Ovaj problem se može rešiti prolaskom kroz petlju redom od 1-n i proverom svakog broja da li je prost pomoću funkcije koja određuje da li je poslati broj prost:
bool isProst(long long n)
{
if(n==1)
return false;
long long d=2;
while(d*d<=n) {
if(n % d == 0)
{
return false;
}
d=d+1;
}
return true;
}
{
if(n==1)
return false;
long long d=2;
while(d*d<=n) {
if(n % d == 0)
{
return false;
}
d=d+1;
}
return true;
}
Dakle, u glavnoj funkciji bi bilo:
int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i++)
{
if(isProst(i)){
cout << i << endl;
}
}
return 0;
}
{
int n;
cin >> n;
for(int i=1;i<=n;i++)
{
if(isProst(i)){
cout << i << endl;
}
}
return 0;
}
Ova metoda bi je previše spora za veliko n, jer proverava sve brojeve redom.
Ovo se može malo ubrzati ako umesto ispitivanja brojeva redom od 1 do n^1/2 ispitivanje završimo sa brojem što će neznatno ubrzati algoritam.
Pravo ubrzanje ćemo dobiti pomožu Eratostenovog sita.
Algoritam Eratostenovo sito:
On se zasniva na ideji da u jednom prolazu proveravamo više brojeva odjednom. Pretpostavimo da je n=50, tj. da treba proveriti sve brojeve između 1 i 50 da li su prosti:
Ovo se može malo ubrzati ako umesto ispitivanja brojeva redom od 1 do n^1/2 ispitivanje završimo sa brojem što će neznatno ubrzati algoritam.
Pravo ubrzanje ćemo dobiti pomožu Eratostenovog sita.
Algoritam Eratostenovo sito:
On se zasniva na ideji da u jednom prolazu proveravamo više brojeva odjednom. Pretpostavimo da je n=50, tj. da treba proveriti sve brojeve između 1 i 50 da li su prosti:
Slika 1: Eratostenovo sito primer: Određivanje prostih brojeva na segmentu 1-50
Uzmimo prvi potencijalni delilac broja 50 koji je sigurno prost broj i sklonimo iz niza sve brojeve koji su deljivi sa ovim potencijalnim deliocem. To je broj 2. Brojeve iz niza sklanjamo jer oni sigurno nisu prosti brojevi, jer su deljivi sa 2, osim sa 1 i sa samim sobom. Ovo bi moglo da se reši for petljom u kojoj tekuća promenljiva i menja od 2 do 50^1/2 ~ 7.07 ~ 7. Dakle poslednji prost broj koji će biti delilac je 7. Posle uklanjanja brojeva deljivih sa 2 stanje je sledeće:
Slika 2: Eratostenovo sito primer-uklanjanje sadržalaca broja 2 koji su veći od 2
Ovaj postupak ponavljame sa sledećim ne uklonjenim brojem. Ako broj prethodno nije uklonjen to znači da je prost. Sada ćemo dakle ukloniti sve brojeve koji su veći od 3 i koji su deljivi sa 3. Posle toga ostaće:
Slika 3: Eratostenovo sito primer-uklanjanje sadržalaca broja 3 koji su veći od 3
Sada ćemo dakle ukloniti sve brojeve koji su veći od 5 i koji su deljivi sa 5. Posle toga ostaće:
Slika 4: Eratostenovo sito primer-uklanjanje sadržalaca broja 5 koji su veći od 5
Ostaje da se uklone svi brojevi koji su veći od 7 i koji su deljivi sa 7. To je u ovom primeru samo broj 49. Posle toga ostaće:
Slika 5: Eratostenovo sito primer-uklanjanje sadržalaca broja 7 koji su veći od 7
Brojevi koji su ostali su prosti brojevi.
Eratostenovo sito - kod
Funkcija koja uklanja ove (ne proste)brojeve bi izgledala:
void eratosten(int n)
{
for(int i=2; i < sqrt(n); i++)
{
if(P[i])
{
for(int j=i; j < n/i; j++)
{
P[i*j]=false;
}
}
}
}
{
for(int i=2; i < sqrt(n); i++)
{
if(P[i])
{
for(int j=i; j < n/i; j++)
{
P[i*j]=false;
}
}
}
}
Tekući element u for petlji je delilac za koji proveravamo da li su brojevi koje potencijalno treba ukloniti deljivi sa istim. Pamćenje brojeva koji su preostali vršimo pomoću niza P. Prvo se proverava da li broj koji je potencijalni delilac još uvek u nizu. Ako jeste on je delilac sa kojim ćemo uklanjati njegove sadržaoce. Ako nije, onda taj broj ne može biti delilac jer nije prost.
Ako jeste delilac, onda vršimo proveru kroz for petlju za brojeve počev od kvadrata delioca. Brojevi x izmeću delioca i kvadrata delioca (i< x<i*i) su već provereni od strane prethodnog delioca i njih ne treba proveravati. Broj brojeva koji se uklanja se dobije kao n/i-i. U prethodnom primeru, gde je n=50, a delilac 2 to bi bilo 50/2-2=25-2=23. To je logično jer ima 25 prirodnih brojeva koji su deljivi sa 2 do broja 50, a pošto izuzmemo 1 i2 ostaje 23 broja.
Brojeve uklanjamo tako što postavimo član niza na poziciji jednakoj broju koji se uklanja na false. Posle ponavljanja postupka sa svim deliocima u nizu će na poziciji prostih brojeva ostati vrednost true. Naravno, pre ovog postupka mora se inicijalizovati ceo niz P na true. Glavna metoda bi bila:
Ako jeste delilac, onda vršimo proveru kroz for petlju za brojeve počev od kvadrata delioca. Brojevi x izmeću delioca i kvadrata delioca (i< x<i*i) su već provereni od strane prethodnog delioca i njih ne treba proveravati. Broj brojeva koji se uklanja se dobije kao n/i-i. U prethodnom primeru, gde je n=50, a delilac 2 to bi bilo 50/2-2=25-2=23. To je logično jer ima 25 prirodnih brojeva koji su deljivi sa 2 do broja 50, a pošto izuzmemo 1 i2 ostaje 23 broja.
Brojeve uklanjamo tako što postavimo član niza na poziciji jednakoj broju koji se uklanja na false. Posle ponavljanja postupka sa svim deliocima u nizu će na poziciji prostih brojeva ostati vrednost true. Naravno, pre ovog postupka mora se inicijalizovati ceo niz P na true. Glavna metoda bi bila:
int main()
{
int n;
cin >> n;
for(int i = 1;i < n;i++) {
P[i]=true;
}
eratosten(n);
for(int i = 1; i <= n; i++)
{
if(P[i])
cout << i << endl;
}
return 0;
}
{
int n;
cin >> n;
for(int i = 1;i < n;i++) {
P[i]=true;
}
eratosten(n);
for(int i = 1; i <= n; i++)
{
if(P[i])
cout << i << endl;
}
return 0;
}
Treba u kodu iznad metoda dodati:
#include
#define DIM 1000
using namespace std;
bool P[DIM+1];
#define DIM 1000
using namespace std;
bool P[DIM+1];
Upotreba Eratostenovog sita kod faktorizacije
Da bi neki broj n faktorisali odnosno, da bi rastavili na proste činioce potrebno je da znamo sve proste činioce ak i koliko se oni puta množe pk i tada broj n možemo napisati u sledećem obliku:
n=p1a1*p2a2*...*pkak, za k=1,2,...
npr. ako je n=50
n=21*52=2*5*5
Pomoću Eratostenovog sita možemo prvo odrediti p1,p2,...pk, tj. delioce.
Onda se dalje broj n prvo deli sa p1,ponavljajući deljenje sve dok je ostatak deljiv sa p1, pa se dalje postupak deljenja ponavlja sa p2 itd.
Posmatrajmo primer koji je prikazan na početku, za n=50. Da bi ovaj broj faktorisali mi bi trebali da počnemo da delimo ovaj broj sa njegovim najmanjim deliocem, što je u ovom slučaju broj 2 i da ponavljamo postupak sve dok je ostatak deljenja i dalje deljiv sa 2.
1 ciklus: 50/2=25, ostatak je dakle 25
Broj 25 dalje ne može sa 2.
Dalje se postupak ponavlja sa ostatkom, a to je broj 25 a njegov najmanji delilac je 5:
1 ciklus: 25/5=5, ostatak je 5
2 ciklus: 5/5=1, ostatak je 1
Ovde se proces završava.
Mi možemo iskoristiti algoritam Eratostenovog sita ovde da za svaki broj x odredimo njegov najmanji delilac umesto da ga uklanjamo. U pokazanom primeru to bi bili brojevi 2 i 5.
Dalje bi prikazani postupak deljenja kroz cikluse uradili pomoću while petlje.
Na početku prvo pripremimo nizove:
Onda se dalje broj n prvo deli sa p1,ponavljajući deljenje sve dok je ostatak deljiv sa p1, pa se dalje postupak deljenja ponavlja sa p2 itd.
Posmatrajmo primer koji je prikazan na početku, za n=50. Da bi ovaj broj faktorisali mi bi trebali da počnemo da delimo ovaj broj sa njegovim najmanjim deliocem, što je u ovom slučaju broj 2 i da ponavljamo postupak sve dok je ostatak deljenja i dalje deljiv sa 2.
1 ciklus: 50/2=25, ostatak je dakle 25
Broj 25 dalje ne može sa 2.
Dalje se postupak ponavlja sa ostatkom, a to je broj 25 a njegov najmanji delilac je 5:
1 ciklus: 25/5=5, ostatak je 5
2 ciklus: 5/5=1, ostatak je 1
Ovde se proces završava.
Mi možemo iskoristiti algoritam Eratostenovog sita ovde da za svaki broj x odredimo njegov najmanji delilac umesto da ga uklanjamo. U pokazanom primeru to bi bili brojevi 2 i 5.
Dalje bi prikazani postupak deljenja kroz cikluse uradili pomoću while petlje.
Na početku prvo pripremimo nizove:
#include < iostream >
using namespace std;
#include< math.h >
#define DIM 1000
using namespace std;
int D[DIM+1];
int a[DIM+1];
int p[DIM+1];
using namespace std;
#include< math.h >
#define DIM 1000
using namespace std;
int D[DIM+1];
int a[DIM+1];
int p[DIM+1];
Funkcija koja određuje najmanje delioce brojeva:
void eratosten(int n)
{
{
for(int i = 1; i <= n; i++)
{
for(int i = 2; i < sqrt(n); i++)
{
}{
D[i]=i;
}for(int i = 2; i < sqrt(n); i++)
{
if(D[i]==i)
{
}{
for(int j = i; j <= n/i; j++)
{
}{
/*Looking for a smaller number divider "(i*j)" i "i"*/
if(D[i] < D[i*j])/*If the divisor of the tested number is smaller than the divisor of his own divisor*/
}if(D[i] < D[i*j])/*If the divisor of the tested number is smaller than the divisor of his own divisor*/
D[i*j]=D[i];
U prvoj petlji postavljamo delioce za sve brojeve da budu oni sami(brojevi su deljivi sa samim sobom). Ovo će ostati najmanji delioci ako se radi o prostim brojevima. Dalje, za brojeve 2 do √n , gledamo redosled njihovih najmanje delioca. Ako nisu prosti brojevi, oni će u posmatranom slučaju biti uklonjeni od strane njihovog najmanjeg delioca, najmanji delilac je "i", za broj (i * j). Na primer, za broj 8 najmanji delilac je 2, a broj 8 u petlji je kao 2 * 4, pa je i = 2, j = 4. U početnom nizu D [8] = 8, D [ 2] = 2 i posle uslova testiranja ako je (D [2] < D [2 * 4]) ... nova vrednost D [8] = 2, a ovo je njen najmanji delilac. Sada kada znamo sve najmanje deljivce, faktorizacija se može izvršiti:
int faktorizacija(int x)
{
int k=0;
while(x > 1)
{
k=k+1;
p[k]=D[x];
a[k]=0;
while(x%p[k]==0)/*Deli sa najmanjim deliocem dok može*/
{
x=x/p[k];
a[k]=a[k]+1;
}
}
return k;
}
{
int k=0;
while(x > 1)
{
k=k+1;
p[k]=D[x];
a[k]=0;
while(x%p[k]==0)/*Deli sa najmanjim deliocem dok može*/
{
x=x/p[k];
a[k]=a[k]+1;
}
}
return k;
}
Elementi niz p predstavljaju redom najmanje delioce onog broja x koji treba da se faktoriše. U prvoj iteraciji spoljašnje while petlje to je početni broj x, u drugoj je ostatak deljenja koji ostaje nakon deljenja sa najmanjim deliocem kroz unutrašnju while petlju. Proces se ponavlja sve dok x ne dođe do 1.
Korišćenje Eratostenovog sita za faktorizaciju se koristi kada imamo mnogo brojeva koje treba faktorisati. Npr za početni broj n, ako treba da se faktorišu svi brojevi od 2-n, ova metoda je pogodna. Glavna metoda koja bi ovo odradila biće:
Korišćenje Eratostenovog sita za faktorizaciju se koristi kada imamo mnogo brojeva koje treba faktorisati. Npr za početni broj n, ako treba da se faktorišu svi brojevi od 2-n, ova metoda je pogodna. Glavna metoda koja bi ovo odradila biće:
int main()
{
int n,k;
cin >> n;
eratosten(n);
for(int i = 2; i <= n; i++)
{
k=faktorizacija(i);
for(int j = 1; j <= k; j++)
{
cout << i << "= " << p[j] << "^" << a[j];
if(j != k)
cout << "*";
else
cout << ";";
}
cout << endl;
}
return 0;
}
{
int n,k;
cin >> n;
eratosten(n);
for(int i = 2; i <= n; i++)
{
k=faktorizacija(i);
for(int j = 1; j <= k; j++)
{
cout << i << "= " << p[j] << "^" << a[j];
if(j != k)
cout << "*";
else
cout << ";";
}
cout << endl;
}
return 0;
}
|
Sledeće
Euklidov algoritam >| |