Prost broj
Izvor Wikipedia, besplatna enciklopedija ( http://sr.wikipedia.org/)
Prost broj je prirodan broj veći od jedan, deljiv samo brojem jedan i samim sobom. Pod terminom deljiv se podrazumeva da je jedan broj deljiv drugim, ukoliko je ostatak deljenja dva broja jednak nuli.
Prosti brojevi su na primer: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, ...
Prostih brojeva ima beskonačno mnogo. Najmanji je broj dva. Osim broja dva svi ostali prosti brojevi su i neparni brojevi.
Naučna disciplina koja se bavi osobinama prostih brojeva se naziva teorija brojeva (^).
Generator prostih brojeva
Program "Generator prostih brojeva" je namenjen za pronalaženje prostih brojeva u okviru zadatog opsega brojeva.
Proste brojeve pronalazi tako što prvo vrši odabir potencijalnog prostog broja, broja kandidata, koji se nalazi u okviru zadatog opsega brojeva, a zatim i njegovo testiranje, utvrđivanje, da li je prost broj ili nije. I jedan i drugi korak zavise od vrste i varijante odabranog algoritma. U programu je obrađeno sedam različitih rešenja algoritama za pronalaženje prostih brojeva. Test algoritam 1 je osnovna verzija algoritma koji prati elementarnu matematičku logiku u pronalaženju prostih brojeva, a Test algoritmi 2, 3 i 4 su optimizovane verzije osnovnog rešenja. Sledeća tri algoritma su Eratostenovo sito (^), Sundaramovo sito (^) i Atkinsonovo sito (^). Sva tri su zasnovana na matematičkoj teoriji sita (^) za pronalaženje prostih brojeva i razlikuju se po brzini i količini utrošene memorije.
Svi algoritmi su u okviru programa detaljno objašnjeni. Program dozvoljava maksimalnu veličinu opsega brojeva od broja dva do jedne milijarde. Ukoliko imate sporiji kompjuter ne pokušavajte sa suviše velikim opsegom. Za prva tri algoritma preporuka je da opseg ne bude veći od dva do jednog miliona, kada je neophodno više minuta za pronalaženje svih prostih brojeva. Klikom na sliku možete preuzeti besplatnu verziju programa, a u okviru priloga na dnu strane se nalazi i open source rešenje za IDE SharpDevelop C# (^), koje možete preuzeti i menjati po želji. Za ispravan rad programa neophodan je .Net framework 4.0 ( ^ ) !
Postoje mnogi algoritmi za pronalaženje prostih brojeva. U zavisnosti od odabranog algoritma za pronalaženje prostih brojeva, zavisi i efikasnost kompjuterskog programa. Termin efikasnost se ovde odnosi na brzinu i utrošak memorije, za generisanje prostih brojeva.
Analizom većine algoritama izdvojena su dva glavna koraka:
1. Odabir broja iz opsega brojeva za koji se predpostavlja da je prost broj.
2. Testiranje odabranog broja da li je prost ili ne, i pamćenje rezultata.
Ova dva koraka su međusobno zavisna, posebno kada je optimizacija u pitanju.
Prvi korak može biti rešen na više načina.
Prostom petljom koja počinje od najmanjeg broja u opsegu, a završava se krajnjim brojem opsega za pretragu. U okviru ove petlje se sukcesivno vrši testiranje svakog broja iz zadatog opsega brojeva da li je prost ili ne.
// pokreni odabir broja za testiranje, prvi korak
for ( int i = početak_opsega; i <= kraj_opsega; i++ )
{
// drugi korak
// testiraj broj i
// ako je prost upamti ga
}
Ovakvo rešenje za prvi korak je osnovno, najsporije i najzahtevnije po pitanju memorije. Optimizacijom odabira broja za testiranje ubrzavamo program. Malo boljom analizom osnovne definicije prostog broja, dolazimo do zaključka da su svi prosti brojevi izuzev prvog broja, broja dva, neparni. Ovo znači da je neophodno testirati samo neparne brojeve u okviru opsega. Ukoliko opseg započinje parnim brojem, početak opsega postavljamo na prvi sledeći neparan broj. Ako opseg započinje brojem dva, broj dva jednostavno isključimo iz prvog koraka i počinjemo od broja tri, a njega naknadno upamtimo kao prvi prost broj. Na ovaj način će se testirati praktično svaki drugi broj u okviru opsega i samim time vreme za pronalaženje prostih brojeva se skraćuje duplo u odnosu na predhodno rešenje.
// proveri da li je početak opsega paran broj
// ako jeste uvećaj ga za jedan
if ( početak_opsega%2 == 0)
{
početak_opsega++;
}
// pokreni odabir broja za testiranje, prvi korak
for ( int i = početak_opsega; i <= kraj_opsega; i+=2 )
{
// drugi korak
// testiraj broj i
// ako je prost upamti ga
}
Dalje ubrzanje programa optimizacijom prvog koraka je moguće malo dubljom matematičkom analizom, koja prevazilazi okvire ovog članka pa neće ni biti objašnjena. Ukoliko ste zainteresovani pročitajte neki od mnogih članaka na internetu posvećenih ovoj temi.
Drugi korak takođe ima više rešenja u praksi.
Na osnovu osnovne definicije prostog broja neophodno je proveriti deljivost odabranog broja iz opsega, sa svim brojevima od broja dva do broja koji je za jedan manji od odabranog broja. Ukoliko je broj deljiv sa nekim od tih brojeva, nije prost. Sam algoritam za testiranje zavisi od odabranog rešenja prvog koraka.
Za pamćenje prostih brojeva koristi se niz tipa BitArray zbog uštede memorije.
// deklariši niz za pamćenje prosth brojeva
// i postavi inicijalnu vrednost svih članova niza na false
BitArray prosti_brojevi = new BitArray(kraj_opsega+1, false);
// pokreni odabir broja za testiranje, prvi korak
for ( int i = početak_opsega; i <= kraj_opsega; i++ )
{
bool jeste_prost = true;
// testiraj broj, drugi korak
for( int j = 2; j < i; j++ )
{
if ( i%j == 0 )
{
jeste_prost = false;
break;
}
}
// ako je prost upamti ga
if ( jeste_prost )
{
prosti_brojevi[i] = true;
}
}
Prikaz pronađenih prostih brojeva se ostvaruje jednostavnim prolaskom kroz niz prosti_brojevi,i ispisivanjem broja pozicije onog člana niza čija je vrednost true.
// prikaži pronađene proste brojeve
for ( int i = početak_opsega; i <= kraj_opsega; i++ )
{
if ( prosti_brojevi[i] )
{
Console.WriteLine(i);
}
}
Ovakvo rešenje testiranja je najsporije, ali je primenjeno zbog načina na koji je rešen prvi korak. Ukoliko se prvi korak optimizuje i odaberu se samo neparni brojevi za testiranje, testiranje brojeva bi takođe bilo samo uz pomoć neparnih brojeva, počevši od broja tri do najvećeg neparnog broja koji je manji od odabranog broja.
// deklariši niz za pamćenje prosth brojeva
// i postavi inicijalnu vrednost svih članova niza na false
BitArray prosti_brojevi = new BitArray(kraj_opsega+1, false);
// proveri da li je početak opsega paran broj
// i ako jeste uvećaj ga za jedan
if ( početak_opsega%2 == 0 )
{
početak_opsega++;
}
// pokreni odabir broja za testiranje, prvi korak
for( int i = početak_opsega; i <= kraj_opsega; i+=2)
{
bool jeste_prost = true;
// testiraj broj, drugi korak
for ( int j = 3; j < i; j+=2)
{
if ( i%j ==0 )
{
jeste_prost = false;
break;
}
}
// ako je prost upamti ga
if ( jeste_prost )
{
prosti_brojevi[i] = true;
}
}
Ovako optimizovana oba koraka duplo ubrzavaju pronalaženje prostih brojeva u zadatom opsegu. Postoje razni algoritmi sa svojim implementacijama u okviru programskog koda koji su efikasniji, i zasnovani na drugačijem pristupu rešavanja ovog problema.
U prilogu se nalazi 'Generator prostih brojeva open source.zip' arhiva koja sadrži kompletan programski kod koji možete preuzeti i u okviru koga se nalazi sedam detaljno opisanih varijanti algoritama za pronalaženje prostih brojeva.
Sve najbolje, Autor