Suuri alkulukujen metsästyskilpailu

Onko taipuvaisuutta nörttiyteen? Saa esittää omia nörtti-projekteja
Avatar
Keckuli
Reactions:
Viestit: 415
Liittynyt: 29 Marras 2022, 22:04
Paikkakunta: Helsinki
Viesti:

Suuri alkulukujen metsästyskilpailu

Viesti Kirjoittaja Keckuli »

Julistan kilpailun alkaneeksi. Ketkä ilmoittauvat mukaan? Palkinnoksi mainetta ja kunniaa.

Kuka palstalla olevista koodareista laskee suurimman alkuluvun? Koodi pitää laittaa näkyviin, muutenhan luku voidaan käydä hakemassa vaikka Wolframista tms. jostain netistä.

Mulla on jo yks ajo menossa. Saa nähdä kauan jaksan odottaa. En vielä osaa arvioida kauan ajo kestää. Etsin lukua miljardi*miljardi-1 pienempää alkulukua. Tähän asti ohjelma on tulostanut:

Luku 999999999999999999 ei ole alkuluku
Luku 999999999999999997 ei ole alkuluku
Luku 999999999999999995 ei ole alkuluku
Luku 999999999999999993 ei ole alkuluku
Luku 999999999999999991 ei ole alkuluku

Nyt se on nyt minuuttikaupalla tutkinut luvun 999999999999999989 alkuluvullisuutta. Ennustan siis, että se on alkuluku, mutta ans kattoo ny.
Noin näin minä ajattelen
Avatar
Keckuli
Reactions:
Viestit: 415
Liittynyt: 29 Marras 2022, 22:04
Paikkakunta: Helsinki
Viesti:

Re: Suuri alkulukujen metsästyskilpailu

Viesti Kirjoittaja Keckuli »

Jouduin pysäyttämään ohjelman. Mod funktio ei taida toimia liian suurille BigDecimal tyypin luvuille. Tähän asti suurin löytämäni alkuluku on ainoastaan 1 miljardi 73 miljoonaa 348 tuhatta 629 :( Tais tulla koneen muistikapasiteettikin vastaan. Ja muutin myös ohjelman toimintaperiaatteen nopeammaksi, mut en ny ala selittelemään...

Koodi: Valitse kaikki

Program Alkulukujenmetsastys;
uses math,sysutils,DateUtils,bigdecimalmath;
CONST maxind = 32762; //lasketaan lukua maxind pienemmät alkuluvut
VAR	  taulukko	: ARRAY[1..maxind] OF BOOLEAN;
	alkuluvut: ARRAY[1..maxind] OF BigDecimal;
	lkm, ind, luku, indeksi:	Longword;	
	neliojuuri:	Float;
	aika1, aika2	:	Double;
	ehdokas: BigDecimal;
	str: array [1..80] of char;
function onalkuluku(luku:BigDecimal):boolean; {Kun Erasthoneen seulalla ollaan laskettu
totuusarvo luvun n alkuluvullisuudesta taulukkoon taulukko[1..maxind], niin sen avulla
lasketaan onko parametri 'luku' alkuluku.}
var indeksi2: Integer;
	onse: boolean;
begin
	indeksi2:=1;
	if (luku mod alkuluvut[indeksi2]) = 0 then onse:=false else
		begin
			indeksi:=2;
			onse:=true;
			while (indeksi2 <= maxind) and onse do
				begin
					if (luku mod alkuluvut[indeksi2]) = 0 then onse:=false;	
					indeksi2:=indeksi2+1;
				end;
		end;
	onalkuluku:=onse;
end;
begin
	aika1:=Now;
	lkm:=maxind;
	neliojuuri:= Sqrt(lkm);
	for ind:=2 to maxind do taulukko[ind]:=true; {oletetaan kaikki alkuluvuiksi}
	taulukko[1]:= false;
	luku:=2;
	ind:=luku;
	while ind<=lkm do {poistetaan 2:n monikerrat}
		begin
			taulukko[ind]:= false; 
			ind:=ind+2; 
		end;
	while (luku < neliojuuri) do
		begin
			while (taulukko[luku] = false) and (luku < neliojuuri) do 
			{etsitään seuraava alkuluku}
			luku:=luku + 1;
			ind:=luku + luku;
			while ind < lkm do {poistetaan sen monikerrat}
				begin
					taulukko[ind]:= false;
					ind:=ind+luku;
				end;
			luku:= luku + 1;
		end;
	taulukko[2]:= true;
	{Nyt on taulukoitu miljoonaa pienempien lukujen alkuluku totuusarvo.
	Taulukoidaan alkuluvut}
	indeksi:=1;
	for ind:=1 to maxind do 
		begin
			if taulukko[ind] then
			begin
				alkuluvut[indeksi]:=ind;
				indeksi:=indeksi+1;
			end;
		end;
	
	//Tutkitaan lukujen maxind*maxind-1:sta lukuun maxind*maxind-200 alkuluvullisuutta
	ehdokas:=maxind*maxind-1;
	while ehdokas>=(maxind*maxind-300) do 
		begin
			if onalkuluku(ehdokas) then
				begin
					str:=BigDecimalToStr(ehdokas);
					writeln('Luku ', str, ' on alkuluku');
				end
			else
			begin
				//str:=BigDecimalToStr(ehdokas);
				//writeln('Luku ', str, ' ei ole alkuluku');
			end;
			ehdokas:=ehdokas-2;
		end;
	 aika2:=Now;
	 Writeln((aika2-aika1)*86400,' sekuntia.');
end.
Noin näin minä ajattelen
Vastaa Viestiin