Hódító / Queosia forum

Hódító / Queosia forum (http://forum.hodito.hu/index.php)

- PC (hardver, szoftver, játékok stb.) (http://forum.hodito.hu/forumdisplay.php?f=28)

- - Programozás (http://forum.hodito.hu/showthread.php?t=4435)

Quote:

Originally Posted by tulip (Post 285275)

É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 :)

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

Quote:

Originally Posted by Redback (Post 285008)

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.

Quote:

Originally Posted by Valezius (Post 285342)

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.

Quote:

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.

Quote:

Originally Posted by Valezius (Post 285352)

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

óbasszus, tényleg. Fáradt vagyok, bocsi. Csodálkoztam is, hogy meg tudlak cáfolni :D:D De sajna nem :)

Quote:

Originally Posted by Redback (Post 285335)

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

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

Quote:

Originally Posted by Valezius (Post 285342)

Ha nem tévedek, akkor 10^8-ig kb 5,5 millió prím van.

Futási idő 1 perc és 19 másodperc:
10^8-ig pontosan 5.761.455 db prím szám van. :)

Quote:

Originally Posted by tulip (Post 285412)

Futási idő 1 perc és 19 másodperc:
10^8-ig pontosan 5.761.455 db prím szám van. :)

megnézem az én pascalos buher módszerem mennyi ideig keresi :) Biztos több idő lesz, sajnos :( Te miben írtad? C?

Quote:

Originally Posted by Redback (Post 285417)

megnézem az én pascalos buher módszerem mennyi ideig keresi :) Biztos több idő lesz, sajnos :( Te miben írtad? C?

Átírtam C-re a Te algoritmusodat lényegi változtatás nélkül és 4 perc 8 másodperc alatt futott le. (Ez 64 bites linux alatt futott, a NetBeans mérte az időt E5200-as procival.) C++-ról viszont az enyémet nem tudom átírni pascalra, mert objektum-orientáltan írtam és nem tudok annyira pascal-ul. :)
Így néz ki a Tied, hogy lásd, nem változtattam semmit:

#include <stdlib.h>
#include <math.h>
#include <stdio.h>

bool prim(long unsigned long szam) {
long unsigned long gyok, i;
gyok = round(sqrt(szam));
i=3;
while (i<=gyok) {
if (szam % i == 0) return false;
i++;
i++;
}
return true;
}

int main(int argc, char** argv) {
unsigned long k = 1;
for (long unsigned long i = 2; i < 50000000 ; i++) {
if (prim(i*2-1)) {
k++;
}
}
printf("%d", k);
printf("\n");
return (EXIT_SUCCESS);
}