 Keď už sa na svojich stránkach venujem prvočíslam, bolo by vhodné si tu uviesť program, ktorý prvočísla generuje. Konkrétne tento generátor vám bez problémov nájde všetky prvočísla od dvojky po jednu miliardu - do 1 000 000 000. Napísal som ho ako konzolovú aplikáciu v C#.
Skladá sa v podstate z dvoch častí: najprv si hrubou silou vygenerujeme prvočísla od trojky vyššie (prečo od trojky vysvetlím nižšie), potom pomocou tejto základnej sady prvočísel bude program generovať ostatné prvočísla.
Článok s prvočíslami môžete nájsť pod týmto odkazom. Rôzne iné zaujímavosti o prvočíslach nájdete v tomto článku.
Program sa sa pokúsil urobiť dosť jednoduchý a preto som neoptimalizoval celkom všetko. Jednu základnú optimalizáciu som si však neodpustil: keďže vieme, že všetky párne čísla sú deliteľné dvomi, tak okrem samotnej dvojky by sme nenašli ani jedno párne prvočíslo. Preto dvojku vyriešime len tak ručne-stručne a algoritmus sa zaoberá len nepárnymi číslami.
Aby sme zistili, či je skúmané číslo prvočíslom, delíme ho číslami a pozorujeme, či je deliteľné (bezo zvyšku) len jednotkou a sebou samým. No a tu prichádza do hry druhá optimalizácia, ktorá je však skôr taká samozrejmá vec: skúmané čísla delíme len prvočíslami (pretože iné čísla by boli len násobkami týchto prvočísel) a aj to len od trojky (keďže v našom generátore vôbec neskúmame párne čísla, tak neskúmame deliteľnosť dvojkou) po odmocninu zo skúmaného čísla.
Predošlá veta bola tak trochu na zadrhnutie. Dajme tomu, že skúšame číslo 193. Nie je párne, takže nevieme hneď pohľadom určiť, či je alebo nie je prvočíslo. Budeme sa ho snažiť deliť prvočíslami: 3 - nedá sa, 5 - tiež, 7 - tiež, 11 - tiež sa nedá, atď. až sa prepracujeme k prvočíslu 13, ktoré je posledné menšie než odmocnina zo 193 (13.892). Pokiaľ sa nedá vydeliť ani týmto číslom (čo sa teda nedá), tak už ďalej ani nemusíme skúšať - môžeme prehlásiť, že 193 je prvočíslo.
Prečo? Načo by nám bolo skúšať či je číslo 21 deliteľné 7, keď sme už skôr zistili, že je deliteľné 3? Vždy pôjdu v pároch - jeden deliteľ menší než odmocnina, a druhý ten väčší (č.21 - 3x7, alebo 7x3). Alebo budú obidva rovnaké - ak sa rovnajú odmocnine (ako napr. 25 - 5x5, keďže 5 je jeho odmocnina).
Ak sme teda nenašli prvočíselného deliteľa menšieho ako odmocnina zo skúmaného čísla, tak zaručene nenájdeme ani toho väčšieho deliteľa - tak načo zbytočne hľadať, počítať?
Teda: v prvej fáze si nadpočítame prvočísla napríklad po číslo 31622 (ktoré je zaokrúhlene odmocnina z jednej miliardy), keďže ich nie je až tak veľa - iba pár tisíc a s tým si vie dnešný počítač poradiť šmahom ruky - toto urobíme iba so základnou optimalizáciou, že skáčeme ponad všetky párne čísla. Potom, pomocou tejto sady prvočísel vieme overovať, či je akékoľvek číslo až po 31623^2 (niečo cez miliardu) prvočíslom už spomínaným spôsobom: delíme prvočíslami od trojky (pamätajme, párne čísla totálne ignorujeme) až po odmocninu zo skúmaného čísla.
Čiže ak by sme zrušili podmienku z while-smyčky a nahradili ju len hodnotou TRUE: while (true) {...} nariadku 80, náš program by šiel a šiel a vypisoval prvočísla od dvojky až po miliardu. Potom by skončil katastrofickou chybou, ktorú náš program sám vyhodí na riadku 50, ak by sme sa pokúšali overiť si prvočíselnosť čísla vyššieho než jedna miliarda. Ale to by nejakú dobu trvalo...
using System;
using System.Collections.Generic;
namespace Prvočísla
{
class Program
{
//pripravme si niekoľko prvočísel
//číslo dva je svojim spôsobom špeciálne, keďže to je jediné *párne* prvočíslo
//keďže náš algoritmus ignoruje všetky párne čísla, dvojku si tu musíme vlastnoručne pripísať
private IList prvočísla = new List() { 2, 3 };
private readonly int MAXIMUM_PRE_TENTO_PROGRAM = 1000000000;
private readonly int ODMOCNINA_MAXIMA = 31622;
public Program()
{
for (
int i = 5;//začnime od 5, keďže 2,3 je v zozname už od začiaktu a 4 je párne číslo
i <= ODMOCNINA_MAXIMA; //keby sme zašli za odmocninu tak môžeme končiť
i += 2 //zaujímame sa len o nepárne čísla, takže krokujeme po dvoch
)
{
if (!dáSaVydeliťPrvočíslom(i))
{
prvočísla.Add(i);
}
}
}
private bool dáSaVydeliťPrvočíslom(int nepárneČíslo)
{
//začíname od prvočísla "3" pri indexe 1 lebo nechceme deliť číslo
// dvojkou (keďže argument je vždy nepárne číslo nemusíme deliť dvomi)
for (int idx = 1; idx < prvočísla.Count; idx++)
{
if (nepárneČíslo % prvočísla[idx] == 0) //pokiaľ sme delili bezo zvyšku
{
return true;
}
}
return false;
}
private bool jePrvočíslo(int číslo)
{
//uistime sa, že skúmané číslo je v rámci našich možností
if (číslo > MAXIMUM_PRE_TENTO_PROGRAM)
{
throw new ArgumentException(string.Format("Tento program vie určiť prvočíla len do {0} miliónov", MAXIMUM_PRE_TENTO_PROGRAM));
}
//budeme skúmané číslo deliť prvočíslami až po jeho odmocninu
int odmocnina = (int)Math.Sqrt(číslo);
int idx = 1;
while (prvočísla[idx] <= odmocnina) //a ideme na vec, skúšame deliť predpočítanými prvočíslami
{
if (číslo % prvočísla[idx] == 0)
{
return false;
}
idx++;
}
//skúmané číslo je prvočíslo, pokiaľ sa nám ho nepodarilo rozdeliť žiadnym iným prvočíslom od 2 po jeho odmocninu
return true;
}
//tu sa spúšťa program
static void Main(string[] args)
{
Program program = new Program();
//dvojka je špeciálna, lebo je to párne prvočíslo
Console.Write("2, ");
//syp prvočisla
int skúšanéČíslo = 3; //1 nie je prvočíslo, 2 sme vypísali, začneme teda od 3
while (skúšanéČíslo < 10000000) //pozrime si len čísla po desať miliónov
{
//pozor, algoritmus je stavaný tak, že očakáva nepárne čísla, t.j. nedelí dvojkou
if (program.jePrvočíslo(skúšanéČíslo))
{
Console.Write(skúšanéČíslo + ", ");
}
skúšanéČíslo += 2; //testujeme len nepárne čísla
}
}
}
}
Centrálnou operáciou v tomto programe je delenie a zisťovanie zvyšku po delení. V C# sa na zistenie zvyšku po delení používa operátor %. Preto využívame podmienku "if (číslo % prvočísla[idx] == 0)", ktorá keby bola splnená, znamenalo by to, že sa nám podarilo číslo úspešne vydeliť bezo zvyšku jedným z prvočísel na zozname.
Otvorte si Visual Studio, vytvorte si nový C# projekt typu konzolovej aplikácie (Console Application) a potom nahraďte nový prázdny program vyššie uvedeným kódom tohto programu. Spustíme stlačením Ctrl+F5 (bez debuggeru to ide rýchlejšie) a pozeráme ako hŕby prvočísel zasypávajú našu obrazovku. Stlačením "Ctrl+C" môžete prerušiť beh konzolovej aplikácie v akomkoľvek bode vykonávania programu.
Alebo si stiahnite už skompilovanú verziu tohto generátora prvočísel. Po spustení program začne sypať prvočísla na obrazovku. Poradím vám ešte, že pozastaviť toto sypanie na momentík môžete kliknutím na posuvník na pravej strane okna. Stlačením Ctrl+C ukončíte program kedykoľvek vás začne nudiť (keďže skompilovaná verzia bude generovať čísla až po miliardu, tak to bude hodnú chvíľu trvať, takže celkom určite budete program končiť práve stlačením Ctrl+C).
Ešte jedna rada, program môžete spustiť tak, aby všetky vygenerované prvočísla boli zapisované do súboru, namiesto priamo na obrazovku. Touto metódou budú prvočísla vygenerované omnoho rýchlejšie. Ako na vec? Zájdeme do príkazového riadku "Windows-tlačidlo"+R >> vpíšeme "cmd". Zobrazí sa príkazový riadok. Navigujeme k programu pomocou príkazu CD (change directory) a potom ho spustíme príkazom:
c:\downloads>Prvočísla.exe > C:\mojePrvocisla.txt
A ešte skrátená verzia tohto programu, bez komentárov a rôznych riadkov naviac:
using System;
using System.Collections.Generic;
namespace Prvočísla
{
class Program
{
private IList prvočísla = new List() { 2, 3 };
private readonly int MAXIMUM_PRE_TENTO_PROGRAM = 1000000000;
private readonly int ODMOCNINA_MAXIMA = 31622;
public Program()
{
for (int i = 5; i <= ODMOCNINA_MAXIMA; i += 2)
{
if (!dáSaVydeliťPrvočíslom(i)) prvočísla.Add(i);
}
}
private bool dáSaVydeliťPrvočíslom(int nepárneČíslo)
{
for (int idx = 1; idx < prvočísla.Count; idx++)
{
if (nepárneČíslo % prvočísla[idx] == 0) return true;
}
return false;
}
private bool jePrvočíslo(int číslo)
{
if (číslo > MAXIMUM_PRE_TENTO_PROGRAM)
{
throw new ArgumentException(string.Format("Tento program vie určiť prvočíla len do {0} miliónov", MAXIMUM_PRE_TENTO_PROGRAM));
}
int odmocnina = (int)Math.Sqrt(číslo);
int idx = 1;
while (prvočísla[idx] <= odmocnina)
{
if (číslo % prvočísla[idx] == 0) return false;
idx++;
}
return true;
}
static void Main(string[] args)
{
Program program = new Program();
Console.Write("2, ");
int skúšanéČíslo = 3;
while (skúšanéČíslo < 10000000)
{
if (program.jePrvočíslo(skúšanéČíslo))
{
Console.Write(skúšanéČíslo + ", ");
}
skúšanéČíslo += 2;
}
}
}
}
Veselé programovanie, či hranie sa s prvočíslami!
Článok s prvočíslami môžete nájsť pod týmto odkazom. Rôzne iné zaujímavosti o prvočíslach nájdete v tomto článku. |
