Programozás

[Redback]

Originally Posted by tulip

Azt tanultam, hogy Eratoszthenész szitája a leggyorsabb ismert prímszám kereső algoritmus. Ha igazán gyorsat szeretnék írni N=10-re, akkor 10^10-nek a gyökéig előállítanám Eratoszthenész szitájával a prím számokat, majd az így megtalált prím számokkal osztogatnám végig a kérdéses intervallumokat. Ha többmagos a processzor, akkor természetesen több szálra tenném ezt a második lépést. Szerintem ez bőven belefér 1 percbe 10 jegy esetén.

a pascalban csak 2^32-en méretű lehet egy tömb, ez 4,2 milliárd. 14 számjegyű szám gyökéig bőven több, mint 4,2 milliárd prímszám van, szerintem.

[tulip]

Originally Posted by Redback

a pascalban csak 2^32-en méretű lehet egy tömb, ez 4,2 milliárd. 14 számjegyű szám gyökéig bőven több, mint 4,2 milliárd prímszám van, szerintem.

Bocs, csak a 10 jegyűeken gondolkodtam, nem a teljes feladatot, mert csak arra mondtál 1 perces korlátot.

Úgy emlékeztem, hogy pascalban nem is lehetett 2^16-nál nagyobb tömböt definiálni. Helyette megoldható mutatókkal. C++-ban és Java-ban viszont 10 jegyűek gyökéig haladva a számokkal szerintem még belefér, mert az csak 100.000.

A 14 jegyű szám esetén nem gondolkodtam. Ahhoz legfeljebb gyök(10^14)=10 millió adatot kellene a memóriában tárolni. Azt hiszem, ennek inkább már C++-ban esnék neki mutatókkal, az még simán lekezel ennyit.

[Redback]

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

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

[Valezius]

Originally Posted by Redback

a pascalban csak 2^32-en méretű lehet egy tömb, ez 4,2 milliárd. 14 számjegyű szám gyökéig bőven több, mint 4,2 milliárd prímszám van, szerintem.

A szerintem nagyon kevés
Van egy ismert képlet a prímszámok darabszámára.
Ha nem tévedek, akkor 10^8-ig kb 5,5 millió prím van. (kb minden 18. szám lesz prím.)
10^8-on meg 10^15 gyöke fölött van.

Szóval a 4,2 milliárdos határt bizony nem éri el.

[Redback]

Originally Posted by Valezius

A szerintem nagyon kevés
Van egy ismert képlet a prímszámok darabszámára.
Ha nem tévedek, akkor 10^8-ig kb 5,5 millió prím van. (kb minden 18. szám lesz prím.)
10^8-on meg 10^15 gyöke fölött van.

Szóval a 4,2 milliárdos határt bizony nem éri el.

Kicsit utánaolvasva a dolgonak, a prímszámok darabszáma [0;x] intervallumban: ~(x/ln(x)). Ez a függvény nagyobb x esetén pontosabb értéket ad, és 10 számjegyű számoknál már csak 4,8% az eltérés a prímek valós számától.

10^14-ig ~3.102.103.442.166 prím szám van. Ebből vegyük el, a 10^13-ig lévő prím számok darabszámát, ami kb ~334.072.678.387.
3.102.103.442.166-334.072.678.387=2.768.030.763.779.
Ha nem számoltam el semmit, akkor elvileg több mint 4,2 milliárd 14 számjegyű prímszám van.

[Valezius]

14 számjegyű szám gyökéig bőven több, mint 4,2 milliárd prímszám van, szerintem.

Azt írtad, hogy a gyökéig kell nézni. 10^15-en gyöke tudtommal 10^7,5<10^8.