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
