Programozás

[Redback]

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ó:

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ő:

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