Programozás

[tulip]

Originally Posted by Redback

köszi azért végül sikerült megcsinálnom

É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.

[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

[Redback]

a fermat prímteszttel az a gondom, hogy 2^(10^14)-en szám pedig horribilis memóriát foglalna, ha egyáltalán bele tudnám tuszkolni valami változóba

[tulip]

Originally Posted by Redback

a fermat prímteszttel az a gondom, hogy 2^(10^14)-en szám pedig horribilis memóriát foglalna, ha egyáltalán bele tudnám tuszkolni valami változóba

Igazad van. Használhatatlan. Le is mondtam róla.