Kirjoittaja: Metabolix
Kirjoitettu: 22.11.2015 – 13.12.2015
Tagit: matematiikka, koodi näytille, vinkki
Alkuluku on kokonaisluku, joka on suurempi kuin 1 ja joka ei ole tasan jaollinen muilla luonnollisilla luvuilla kuin itsellään ja 1:llä. Ensimmäiset alkuluvut ovat 2, 3, 5, 7 ja 11. Sen sijaan 4, 6, 8 ja 10 eivät ole alkulukuja, koska ne voi jakaa 2:lla, ja 9 ei ole alkuluku, koska sen voi jakaa 3:lla.
Usein kysytään, onko luku alkuluku. Tämän selvittämiseen on yksinkertainen tapa: koetetaan jakaa luku kaikilla sitä pienemmillä alkuluvuilla, ja jos jakojäännökseksi tulee jossain tapauksessa nolla, luku ei ole alkuluku. Pienin kokeiltava jakaja on 2, joka on ensimmäinen alkuluku. Suurin kokeiltava jakaja on enintään tutkittavan luvun neliöjuuri, koska tämän suuremmilla jakajilla laskun tulokseksi täytyisi tulla vastaavasti neliöjuurta pienempi kokonaisluku. Ei haittaa, vaikka jakolaskua koetettaisiin muillakin luvuilla kuin alkuluvuilla, kunhan kaikki alkuluvut tulevat kokeilluiksi.
Seuraavassa funktiossa on toteutettu alkuluvun tarkastus edellä kuvatulla tavalla.
#include <cmath>
bool on_alkuluku(long luku) {
// Alle 11:n olevia alkulukuja ovat vain 2, 3, 5 ja 7.
if (luku < 11) {
return luku == 2 || luku == 3 || luku == 5 || luku == 7;
}
// Tutkitaan jaollisuus 2:lla ja 3:lla.
if (luku % 2 == 0 || luku % 3 == 0) {
return false;
}
// Tutkitaan silmukassa muut mahdolliset jakajat neliöjuureen saakka.
// Riittää tutkia jakajat 6*n+5 ja 6*n+7 (ts. 6*n+1), koska jakajien
// pitäisi olla alkulukuja mutta 6*n ja 6*n+3 ovat jaollisia 3:lla
// ja 6*n+2 ja 6*n+4 ovat jaollisia 2:lla. (Silmukassa i = 6*n+5.)
long viimeinen = std::sqrt(luku);
for (long i = 5; i <= viimeinen; i += 6) {
if (luku % i == 0 || luku % (i+2) == 0) {
return false;
}
}
return true;
}Funktiota voi käyttää vaikkapa näin:
#include <iostream>
int main() {
std::cout << "Alkulukuja:\n";
int i = 1;
// Tulostetaan 20 riviä.
for (int rivi = 0; rivi < 20; ++rivi) {
// Tulostetaan enintään vähän yli 70-merkkiä riville.
for (int pituus = 0; pituus < 70; ++pituus) {
// Korotetaan i:tä, kunnes löydetään alkuluku.
do i += 1; while (!on_alkuluku(i));
// Tulostetaan alkuluku ja valvotaan rivin pituutta.
std::cout << i << ", ";
pituus += std::floor(std::log10(i)) + 2;
}
// Rivin loppuun tulee rivinvaihto.
std::cout << "\n";
}
}Suurten lukujen kohdalla tämä algoritmi on hidas. Ongelmaan on kehitetty joitain hieman nopeampia ratkaisuja, ja jos sellaiselle on tarvetta, kannattaa etsiä jokin valmis matematiikkakirjasto. Kuitenkin alkulukujen etsintä ja lukujen tekijöiden selvittäminen ovat edelleen (vuonna 2015) tehokasta ratkaisua vailla.
Nätti koodivinkki, mutta nuo kommentit tuntuu vähän oudoilta, kuten:
"selvästi 6*n+2, 6*n+4 ja 6*n+8 ovat jaollisia 2:lla"
Eikös 6*n+8 ole sama asia kuin 6*n+2 ? Jos taas tuo on tarkoituksella, niin miksi 6*n+6 puuttuu välistä. Toisaalta 6*n olisi oikeastikin hyvä mainita.
Yleisesti ottaen tuolla a*n+b esityksellä tuntuu minusta oudolta, jos b >= a.
Heh, enpä tiedä, mistä ajatuskatkoksesta nuo olivat tulleet. Nyt kommentissa ovat oikeat tapaukset (6n, 6n+2, 6n+3, 6n+4).
Tuo on täyttä raa'an voiman käyttöä, eikä siinä ole lainkaan oikeaa osaamista.
lainaus:
Tuo on täyttä raa'an voiman käyttöä, eikä siinä ole lainkaan oikeaa osaamista.
Milloinkas nähdään sinulta koodivinkki kyseisestä aiheesta ilman täyttä raa'an voiman käyttöä kera oikean osaamisen? Eikä tämän vinkin tarkoitus ole olla mikään üüber hieno ja tehokas ratkaisu vaan, kuten tekstissä mainitaan, yksinkertainen ja helposti ymmärrettävä tapa alkulukujen etsimiseen.
lainaus:
Tuo on täyttä raa'an voiman käyttöä, eikä siinä ole lainkaan oikeaa osaamista.
Vinkin oikea osaaminen on algoritmin selvässä toteutuksessa. Tämän monimutkaisempaa koodia alkulukujen tarkastukseen ei yleensä kannata tehdä itse, vaan jos tarvitaan tehokas ratkaisu isoille luvuille, mielestäni oikea ”koodivinkki” on neuvoa lataamaan netistä jokin matematiikkakirjasto.
Kannattaa myös muistaa, että on olemassa probabilistisia alkulukutestejä, kuten Millerin–Rabinin testi, jotka antavat suurella todennäköisyydellä alkuluvun mutta toimii nopeammin kuin deterministiset testit.
Lisäksi Miller-Rabinista voi käyttää determinististä variaatiota, jos kokeiltavat luvut eivät ole mielivaltaisen suuria. Sen toteuttaminen 64-bittisille luvuille ei ole kovinkaan vaikeaa, mutta turha sitä tähän vinkkiin on sotkea.