Quote:
Originally Posted by tulip
Érdekelne, hogy milyen módszerrel oldottad meg, mert én kipróbáltam azt, amit én javasoltam, de úgy már 10 millióig az összes prímszám megkeresése 5 másodpercig tartott, az pedig csak N=7 eset, szóval pillanatnyilag meg sem tudom közelíteni a feladat szerinti N=10 esetet 1 perc alatt. Nem futtattam, de az eredmények alapján kb. 8 óra lenne a futási ideje. 
Kitaláltam egy másik módszert, de az túl bonyolult ahhoz, hogy csak úgy hirtelen összedobjam, és nem is biztos elég gyors.
Most olvastam a Fermat-prímtesztet. Ha csak néhány estre nézzük a Fermat-prímteszttel a számokat, akkor a nem prímek jó eséllyel megbuknak és csak a maradékra kell nézzük meg, hogy valóban prímek-e. Majd kipróbálom valamikor, hogy ez segít-e rajta. |
Azt ugye belekalkuláltad, hogy a számjegyek balról jobbra nem növekedhetnek? Ha igen, akkor elmondom én hogy csináltam:
Egy számgeneráló eljárás és egy eléggé felturbózott (gyökéig osztókat kereső) prímkereső algoritmussal.
Számgeneráló:
Code:
function novekvo(szam : int64; n : byte;ciklus : byte) : boolean;
var i : byte;
Begin
if n>1 then
Begin
for i:=ciklus to 9 do
novekvo(szam*10+i,n-1,i);
End
else
Begin
if ciklus mod 2 = 1 then i:=ciklus
else i:=ciklus+1;
while i<=9 do
Begin
if prim(szam*10+i) then WriteLN(szam*10+i);
Inc(i,2);
End;
End;
End;
primkereső:
Code:
function prim(szam:int64): boolean;
var gyok,i : int64;
Begin
prim:=true;
gyok:=trunc(sqrt(szam));
i:=3;
while i<=gyok do
Begin
if szam mod i = 0 then
Begin
prim:=false;
break;
End;
inc(i,2);
End;
End;
Ha nem vagy benne pascalban, akkor leírom majd pszeudo kódban is