Kirjautuminen

Haku

Tehtävät

Koodit: C++: Alkuluvun tarkastus

Kirjoittaja: Metabolix

Kirjoitettu: 22.11.2015 – 13.12.2015

Tagit: matematiikka, 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.

Kommentit

Grez [23.11.2015 00:54:32]

#

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.

Metabolix [23.11.2015 17:35:10]

#

Heh, enpä tiedä, mistä ajatuskatkoksesta nuo olivat tulleet. Nyt kommentissa ovat oikeat tapaukset (6n, 6n+2, 6n+3, 6n+4).

artist2020 [12.12.2015 09:39:15]

#

Tuo on täyttä raa'an voiman käyttöä, eikä siinä ole lainkaan oikeaa osaamista.

Pessi [12.12.2015 10:03:20]

#

Milloinkas nähdään artist2020 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.

Metabolix [12.12.2015 12:58:42]

#

artist2020, 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.

Jaska [12.12.2015 17:46:27]

#

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.

jlaire [12.12.2015 18:36:31]

#

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.

Kirjoita kommentti

Muista lukea kirjoitusohjeet.
Tietoa sivustosta