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

[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

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

[Redback]

Originally Posted by Valezius

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 De sajna nem

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

[tulip]

Originally Posted by Valezius

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.

[Redback]

Originally Posted by tulip

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?

[tulip]

Originally Posted by Redback

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);
}