Keskustelu: Yleinen keskustelu: Suurta alkulukua etsimään

Program Alkuluku;
uses math,sysutils,DateUtils,bigdecimalmath;
CONST maxind = 1500000000; {lasketaan 1,5 miljardia pienemmät alkuluvut}
VAR	  taulukko	: ARRAY[1..maxind] OF BOOLEAN;

	lkm, luku:	qword;
	ind:	longint;
	neliojuuri	:	Float;
	ehdokas,apuri: qword;
function onalkuluku(luku:qword):boolean;
var indeksi: Longword;
	onse: boolean;
begin
	if (luku mod 2) = 0 then onse:=false else
		begin
			indeksi:=3;
			onse:=true;
			while (indeksi <= Sqrt(luku)) and (onse=true) do
				begin
					if taulukko[indeksi] then
					begin
						if (luku mod indeksi) = 0 then
							begin onse:=false;
							writeln(indeksi);
						end;
					end;
					indeksi:=indeksi+2;
			end;
		end;
	onalkuluku:=onse;
end;
begin
	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 miljardia pienemmät alkuluvut.
	 Tulostetaan sataa pienemmät kokeeksi.}
	for ind:=1 to 100 do
			if taulukko[ind]=true then writeln (ind);
	//Tutkitaan ehdokaslukuja
	apuri:=1;
	while apuri < 100 do
		begin
			ehdokas:=maxind*maxind-apuri;
			if onalkuluku(ehdokas) then
				begin
					writeln(ehdokas,' on alkuluku.')
				end
					else writeln(ehdokas,' ei ole alkuluku.');
			apuri:=apuri+2;
		end;
end.

Program Alkuluku;
uses math,sysutils,DateUtils,bigdecimalmath;
CONST maxind = 1500000000; {lasketaan 1,5 miljardia pienemmät alkuluvut}
VAR	  taulukko	: ARRAY[1..maxind] OF BOOLEAN;
	lkm, luku:	qword;
	ind:	longint;
	neliojuuri	:	Float;
function LucasLehmerTest(p: Integer): Boolean;
var
  s, mersenne: Int64;
  i: Integer;
begin
  if p = 2 then
  begin
    LucasLehmerTest := True;
    Exit;
  end;
  s := 4;
  mersenne := Int64(1) shl p - 1;
  for i := 3 to p do
    s := (s * s - 2) mod mersenne;
  LucasLehmerTest := s = 0;
end;

procedure tulostaMersenne(pot: Int64);
var tulostaluku: bigdecimal;
	indeksi: Int64;
begin
	tulostaluku:=2;
	indeksi:=1;
	while indeksi < pot do
		begin
			tulostaluku:=tulostaluku*2;
			indeksi:=indeksi+1;
		end;
	tulostaluku:=tulostaluku-1;
	writeln(BigDecimalToStr(tulostaluku));
end;


begin
	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;
	writeln('Taulukko valmis');
	//Nyt on taulukoitu 1.5 miljardia pienemmät alkuluvut.
	for ind:=(maxind-3000) to maxind do //tutkitaan lukuja 2^alkuluku LucasLehmerin testillä.
		if taulukko[ind] then
			begin
				if LucasLehmerTest(ind) then
					begin
				    	Writeln('2^', ind, ' - 1 on alkuluku.');
				    	tulostaMersenne(ind);
				    end;
			end;
end.