vladiii Posted October 11, 2007 Report Share Posted October 11, 2007 In primul rand, daca gasiti vreo eroare in codul scris de mine sau vreo greseala de algoritm, va rog sa o mentionati, pentru ca nici eu nu sunt 100% sigur de codul pe care l-am facut.Ok, ce este Algoritmul Miller-Rabin ? Numele sau intreg este: "Testul de primalitate al numerelor Miller-Rabin". Practic verifica daca un numar este prim sau nu. Insa, nu degeaba se numeste test, pentru ca probabilitatea ca raspunsul returnat de program nu este maxima (pow(4,-k)).Si poate va intrebati, de ce sa folosesc acest algoritm, cand pot sa impart numarul la toate numerele mai mici decat sqrt(numar) ? Pai da, dar acesta este mult mai rapid si are o complexitate mai mica Va prezint in continuare codul scris de mine in C (astept imbunatatiri sau corectari):#include <stdlib.h>#include <stdio.h>#include <time.h>#include <conio.h>#include <math.h>int main(){ long numar, s=0, a=0, r, d=0, k, aux1=0, aux2=0, i=0, aux3=0, aux4=0; div_t aux5; printf("Introdu numarul: "); scanf("%d", &numar); printf("\nIntrodu un numar k(probabilitatea este 4 la puterea -k): "); scanf("%d", &k); aux1=numar-1; while(aux1%2 !=1) { if(aux1%2==0) { s++; } aux1=aux1/2; } printf("%ld", (int)pow(2,s)); aux4=(long)pow(2,s); aux5=div(numar-1,aux4); d=aux5.quot; printf("\nPuterea lui 2 este: %ld iar restul este: %ld", s, (long)d); if(numar==2 || numar==3 || numar==5 || numar==7 || numar==11) { printf("\nNumarul este prim"); } else if(numar=4 || numar==6 || numar==8 || numar==9 || numar==10) { printf("\nNumarul nu este prim/ este compus"); } else { srand(time(NULL)); for(i=0;i<k;i++) { a=rand() %(numar-1)+1; aux2=(long)pow(a,d)%numar; for(r=0;r<=s-1;r++) { if(aux2 !=1 & (long)pow(a,pow(2,r)*d)%numar !=numar-1) { aux3=1; } } } if(aux3==1) { printf("\nNumarul este prim"); } else { printf("\nNumarul nu este prim/ este compus"); } } getch(); return 0;}Sper sa va fie de folos la ceva (si ma repet, postati eventualele greseli de algoritm .P.S. Pentru un "accuracy" mai bun puteti sa generati toate numerele A din intervalul [1, numar-1], insa asta va ingreuna timpul de executie (eu am ales numere random).Bibliografie:[url]http://en.wikipedia.org/wiki/Miller-Rabin_primality_test[/url]+[url]http://vladii.wordpress.com[/url] Quote Link to comment Share on other sites More sharing options...
Black Pitbull- Posted October 11, 2007 Report Share Posted October 11, 2007 Mam esti obsedat de asta .... e si la u pe blog si aici ... pune si pe youtube Quote Link to comment Share on other sites More sharing options...