Mit gondoltok a programozási gondolkodásomról?

Valamivel jobb megoldas :

#include <iostream>

using namespace std;

bool isPrim(int num){

bool prim=true;

for(int i=2;i<num;i++){

if(num % i ==0){

prim=false;

break;

}

}

return prim;

}

int main()

{

int a;

do{

cin >>a;

}while(a<1);

for(int i=a;i>0;i--){

if(isPrim(i))

cout<<i <<"\n";

}

cin.clear();

cin.ignore();

cin.get();

}

Amit nem vett észre senki, hogy nem is azt csinálja a program amit kell, vagyis hibás.

Ha N-ig az összes nála kisebb prímet kell megkeresni akkor az Eratoszthenészi szita gyorsabb, ha nem a leggyorsabb.

Végül is hogy az összes prímet vagy összes nem prímet keressük, adott számig, szinte ugyan az a feladat.

Na megy a hülyeség ezerrel.. Fermat álprim teszt csak egy valószinüséget ad meg, nem tudod meg belőle, hogy biztosan prim-e(vagy nem) egy szám. Ráadásul nem egyszerü leprogramozni sem, plusz nem is ilyen nagyságrendü számokon alkalmazzák, hanem olyan nagyságrendre, amikor a hagyományos módszerek már nem használhatóak, cserébe viszont beáldozzák a teljes bizonyosságot :)

Első lépésben már az is sokat javitana a dolgon, ha csak a szám négyzetgyökéig tesztelnéd az osztókkal.

Második lépésben mondjuk átirhatnád szitálásra.

Harmadik lépésben meg csinálhatnál valamiféle cache-t az addig megtalált számokra, mert pl. a user beirja egymás után a 30-at, a 40-et, meg az 50-et, akkor a 30-nál kisebb számokra 2x fut le a teszt teljesen feleslegesen.

Had tegyem tisztába a dolgokat!

"Honnan szedsz ilyen hülyeséget, valószínűség? "

A Fermat-prímteszt minden prímszámról helyesen eldönti hogy prím, viszont vannak számok melyekre prímet ad pedig nem azok, ezek az ún. Fermat-álprímek. Vagyis ha azt adja vissza hogy nem prím akkor tényleg nem az. A Fermat-álprímek viszonylag ritkán fordulnak elő, vagyis ha kísérletet csinálunk a kísérlet a következő:véletlen számokat generálunk az egyenletességi hipotézisnek megfelelően, ha a generált véletlen szám prím a Fermat prímteszt szerint, akkor nagyobb valószínűséggel valóban prím mint nem az. Vagyis valamilyen valószínűséggel helyesen állapítja meg a Fermat prímteszt.

"Ráadásul nem egyszerü leprogramozni sem, plusz nem is ilyen nagyságrendü számokon alkalmazzák, hanem olyan nagyságrendre, amikor a hagyományos módszerek már nem használhatóak"

Nekem kb. 5 perc volt leprogramozni, ezt a prímtesztet unsigned int-re, óriás számokra meg elő kéne keresnem a BigInteger vagy valami ilyesmi nevű osztályomat az unsigned int-et lecserélni arra és kész.

Valóban inkább akkor használják amikor a hagyományos módszerek nem használhatóak, de inkább a Miller–Rabin-teszt-et használják ekkor.

"..cserébe viszont beáldozzák a teljes bizonyosságot"

Ez nem igaz.

Csak hogy ne a levegőbe beszéljek, vettem a fáradságot és megcsináltam a Fermat prímteszet, az Eratoszthenész szitáját, a naiv módszert ahol legfeljebb a négyzetgyökéig ellenőrzi az adott számot.

1-től 10 millióig lefuttattam a következő futási idők lettek (a kiíratás nincs benne):

Naiv módszer:

real 0m11.466s

user 0m11.449s

sys 0m0.000s

A Fermat prímteszt, naiv módszerrel biztosítva a helyességet:

real 0m7.548s

user 0m7.536s

sys 0m0.000s

Simán csak a Fermat prímteszt:

real 0m7.381s

user 0m7.368s

sys 0m0.000s

Eratoszthenész szitája:

real 0m1.059s

user 0m1.052s

sys 0m0.004s

A teljesség kedvéért megemlítem hogy amit a kérdező írt kódot nagyon pazarló, talán órák hosszáig vagy napokig futna (nem próbáltam ki)

Vagyis a nyertes nem más mint az Eratoszthenész szitája, az a sejtésem hogy ez a lehető leggyorsabb ha 1-től N-ig az összes prímet kell megkeresni, más esetben nem feltétlen.