Elektroda.pl
Elektroda.pl
X

Search our partners

Find the latest content on electronic components. Datasheets.com
Elektroda.pl
Please add exception to AdBlock for elektroda.pl.
If you watch the ads, you support portal and users.

[C] Algorytm sita Erastotenesa.

cortez_ 05 Mar 2004 21:18 5162 14
  • #1
    cortez_
    Level 26  
    Potrzebuje waszej rady. Napisalem program, moze niezbyt doskonaly ale to w celach edukacyjnych (no ucze sie programowac w C). Program ma sluzyc wyswietlaniu na snandardowe wyscie liczb rozkladajacych sie tylko na dwa czynniki pierwsze (czyli szuka takich liczb ktore sa iloczynem dwoch liczb pierwszych).
    Program poszukuje liczb pierwszych wg. algorytmu erastotenesa.
    W zwiazku z tym mam kilka pytan do wklejonego ponizej kodu.

    1. po skompilowaniu otrzymalem plik wynikowy az 8Mb (kompilowalem gcc pod linuxem), dlaczego jest on taki duzy i czy da sie zrobic cos zeby byl mniejszy?

    2. czy da sie jeszcze jakos przyspieszyc ten algorytm? dla przeszukiwania zakresu od 0 do 300000 potrzebuje na sprzecie klasy Duron 800Mhz okolo 30 sekund, przeszukiwanie zakresu maksymalnego czyli okolo 8000000 liczb zajmuje pewnie okolo 4 godzin (3500000 przeszukal w okolo 2h) Co nalezaloby zrobic jeszcze zeby go przyspieszyc?

    3. maksymalny rozmiar tablicy na liczby pierwsze jaki udalo mi sie zadeklarowac wynosi 8000000, czy da sie zadeklarowac wieksze tablice?


    Code:
    /******************************************************************************
    
    *Nazwa programu                                                               *
    *                                    Rozklad liczb na czynniki pierwsze       *
    *                                    generuje liczby ktore maja tylko dwa     *
    *                                    czynniki pierwsze                        *
    *Opis danych                                                                  *
    *     -wejsciowych                                                            *
    *                                pobiera z wejscia standardowego gorna granice*
    *     -wyjsciowych                                                            *
    *                                wyprowadza na standardowe wyjscie liczby     *
    *Opis obslugi bledow                                                          *
    *                                    brak                                     *
    *Uwagi                                                                        *
    *                                    algorytm sita erastotenesa               *
    *                                    z usprawnieniami                         *
    *******************************************************************************/


    #include <stdio.h>                          /*Plik naglowkowy  */
    #include <time.h>

    char lista[8000000]={}; //zdefiniujmy pusta tablice w ktorej bedziemy przesiewac liczby pierwsze
                            //aby nie ustawiac na poczatku calej tablicy na wartosc true (1) przyjmijmy ze inicjalna wartosc kazdej komorki=false oznacza ze liczba jest pierwsza
             //liczby NIE PIERWSZE oznaczamy jako true(1) czyli sprawdzanie tablicy bedzie wymagalo operatora negacji aby wartosc true wychodzila tylko dla pierwszych
    int licz(unsigned int granica)  //definiuje funkcje ktora rozklada podana liczbe na czynniki pierwsze
    {
    unsigned long dzielniki[1000];  //tworze tablice w ktorej bede zapamietywal dzielniki podanej liczby
    unsigned int granica3,n,i,licznik,pierwsza,mod,j;



       granica3=granica; //zapamietam jaka zostala podana granica, zmienna granica bede modyfikowal
       n=0;  //liczniki
       i=0;
       licznik=2;
       if (granica<=8000000) pierwsza=!lista[granica]; //jesli podana liczba jest ponizej 8000000 to sprawdzmy czy jest pierwsza
       else
       {
           printf("\nPodana liczba jest wieksza od 8000000. \nNie wiem czy podana liczba jest pierwsza, ale bede probowal ja rozlozyc");
           pierwsza=0;
       }
       if (!pierwsza)  //sprawdzam czy podana liczba jest pierwsza
       {
       while (licznik<=granica)
       {
           while (licznik<=granica) //wez nastepna liczbe pierwsza
           {
          if (!lista[licznik])  //jesli trafilem na liczbe pierwsza zapamietuje ja w zmiennej i
          {
              i=licznik;
              break;
          }
          ++licznik;   //w innym przypadku zwiekszam licznik
          if (licznik%2==0) ++licznik;  // poniewaz liczby pierwsze sa tylko nieparzyste to gdybysmy stali na parzystym liczniku zwiekszamy go
           }
          
           mod=granica%i;  //dziele sprawdzana liczbe przez kolejne liczby pierwsze
           if (mod==0)  //zapiszmy znaleziony dzielnik
           {
          dzielniki[n]=i;//zapisuje dzielnik w tablicy dzielnikow
          n++;//zwiekszam licznik tablicy dzielnikow
          granica=granica/i;//zmniejszam sprawdzana liczbe dzielac przez juz znaleziony dzielnik
          if (n>=3) //jesli ma wiecej niz 2 dzielniki to dajmy sobie spokoj z szukaniem
          {
              break;
              n=10; //maly hak zeby przypadkiem nie wyswietlil nam pozniej smieci to ustawmy ze znalazl DUZO wiecej dzielnikow niz 2
          }   
           }
           else
           {
          ++licznik;//jesli nie znalazl dzielnika to zwieksza licznik
          if (licznik%2==0) ++licznik;//doprowadza licznik do nieparzystosci tak by ograniczyc poszukiwania liczb pierwszych w tablicy tylko do nieparzystych
           }
       }   
       //wyswietlmy tablice dzielnikow jesli sa tylko dwa
       if (n==2) printf("\n%i=%i*%i",granica3,dzielniki[0],dzielniki[1]);   
       }
       return(0);
    }

    int main()    //nasz glowny program
    {
    time_t czas1,czas2; //definiuj typ czas

    unsigned int granica2,licznik,j,k,n,gora;

       printf("\fPodaj gorna granice obliczen [liczba calkowita>2]:   ");
       scanf("%i",&gora);
       printf("\nPodales granice:  %i\n", gora);
       
       printf("\nGeneruje tablice liczb pierwszych");
       time(&czas1); //pobierz aktualny czas

       granica2=8000000;
       if (gora<granica2) granica2=gora;  //nie ma sensu przesiewac 8000000 liczb jesli zalozona granica obliczn jest mniejsza
       licznik=2; //inicjuje licznik
       while (licznik*licznik<=granica2)  //generuje tablice liczb pierwszych algorytmem sita erastotenesa, szukam tylko do pierwiastka kwadratowego z podanej granicy
                      //chyba szybciej bedzie liczyl jesli wykorzystam mnozenia a nie pierwiastkowanie
       {
          if (!lista[licznik])   //jesli trafilismy na liczbe pierwsza to
          {
              j=2;
              while (licznik*j<=granica2)  //wszystkie jej wielokrotnosci skreslamy
              {
             lista[licznik*j]=1; //zaznaczamy ze nie sa pierwsze
             ++j;
              }   
              }
          ++licznik;
       }

       printf("\nGeneruje liczby rozkladajace sie na dwa czynniki pierwsze");
       
       for (k=2;k<=gora;k++)
       {
           if (!((k!=4&&k%4==0)||  //to jest hak ktory przyspiesza obliczenia
                 (k!=6&&k%6==0)||  //nie wchodzimy do bardzo pogmatwanej funkcji licz()
            (k!=9&&k%9==0)||  //jesli liczba ktora mamy na tapecie
            (k!=10&&k%10==0)||//dzieli bez reszty sie przez iloczyn dwoch liczb pierwszych
            (k!=14&&k%14==0)||//a nie jest rowna temu iloczynowi
            (k!=15&&k%15==0)||//slowem jesli istnieja jeszcze inne czynniki pierwsze tej liczby
            (k!=21&&k%21==0)||//bo chcemy szukac tylko rozkladow dwuczynnikowych
            (k!=22&&k%22==0)||
            (k!=25&&k%25==0)||
            (k!=26&&k%26==0))) licz(k); 
    //licz k tylko jesli nie dzieli sie bez reszty przez lioczyn jakis 2 liczb pierwszych, jesli sie dzieli bez reszty a nie jesk ktoras z nich to znaczy ze ma wiecej niz 2 czynniki
       }

       time(&czas2); //pobierz czas konca obliczen
       
       
       printf("\n");   
       
       printf("\nCzas poczatku obliczen: %.24s.", ctime(&czas1));
       printf("\nCzas konca obliczen: %.24s.\n", ctime(&czas2));
       
       return (0);
    }


    Temat zamykam. - arnoldziq
  • #2
    rysgaj
    Level 11  
    Tak na szybko :wink:
    1) Program dlatego (po kompilacji) jest taki duzy, bo:
    char lista[8000000]={};
    (zadeklarowales statyczna 8MB talice - stad rozmiar programu 8MB)

    Mozna (taka tablice) utworzyc dynamicznie, np.:

    char *lista;

    int main()
    {
    ...
    lista=(char *)malloc(8000000);

    ... obliczenia ...

    free(lista);
    ...
    }
  • #3
    cortez_
    Level 26  
    mam jeszcze program ktory liczy tylko liczby pierwsze, zawiera ten fragment algorytmu sita erastotenesa i tyle, tez korzysta ze statycznej tablicy 8Mb i po skompilowaniu zajmuje 11 kilo ;)
    To chyba nie tu jest problem, choc moze sie myle.
    jesli dobrze rozumiem to po uruchomieniu programu tworzona jest w pamieci tablica 8Mb i nie ma to wiele wspolnego z objetoscia kodu wynikowego.

    Zastanawiam sie tez nad jednym czy nie szybszy bylby algorytm, ktory zamiast dzielenia i sprawdzania kazdej liczby po prostu bralby wszystkie kombinacje zadanych liczb pierwszych i tworzyl z nich iloczyny??? Moze to byloby prosciej i szybciej?
  • #4
    Gavian
    Level 14  
    Code:

    char lista[8000000]={};
    Jest to tablica danych inicjowanych natomiast tablica
    Code:

    char lista[8000000];
    jest tablica danych nieinicjowanych. Róznica jest taka że sekcja danych inicjowalnych pamieta wszystkie dane zainicjowane, w tym przypadu 8MB zamych zer. Natomiast sekcja danych nieinicjowanych pamieta tylko wielosc obszaru do zainicjowania. Lepiej tablice pusta zadeklarować char lista[8000000]; bo i tak loader wypełni ja zerami.

    Pozdrawiam
  • #5
    elektryk
    Level 42  
    cortez_ wrote:
    Zastanawiam się tez nad jednym czy nie szybszy bylby algorytm, ktory zamiast dzielenia i sprawdzania kazdej liczby po prostu bralby wszystkie kombinacje zadanych liczb pierwszych i tworzyl z nich iloczyny??? Moze to byloby prosciej i szybciej?
    No właśnie na tym polega sito erastotelesa, bierzesz pierszą liczbe (zaczynasz od 2) i usuwasz z tablicy wszystkie jej wielokrotności, potem liczbe 3 i jej wielokrotności, następna będzie 5 (bo 4 'wyleciala' przy okazji 2).
  • #6
    cortez_
    Level 26  
    Zmiana na char lista[8000000]; podzialala, tzn po kompilacji program zajmuje tylko 12 kilo. Nie rozumiem tego bo w kilku innych programach deklarowalem te tablice identycznie (w zasadzie ten fragment kodu do wyszukiwania liczb pierwszych przekleilem bez zmian) i tamte programy z tablica danych inicjowanych zajmowaly po kompilacji tylko 11 kilo. Czy ktos moze mi to wyjasnic?

    Drugie pytanie to czy mozna zadeklarowac wieksza tablice? Albo zrobic cos zeby taki program mogl przesiac wiecej liczb niz 8000000?

    Do elektryka: Wlasnie zalgorytm erastotenesa zastosowalem do znajdywania liczb pierwszych. Jest z mojego doswiadczenia najszybszy. Liczby te sa zgromadzone w omowionej powyzej tablicy.
    Poniewaz ten program ma szukac dwuczynnikowych rozkladow na liczby pierwsze to pomyslalem zeby odwrocic nieco problem i zamias szukac rozkladu na dwa czynniki, to generowac iloczyny kombinacji dwu liczb pierwszych.

    Sprobuje to zakodowac i dam wam znac.

    Acha no i policzylem szybkosc, zakres 8milionow liczb przeczesal w piec godzin na Duronie 800 pod linuxem ;)

    Pozostaja zatem w stosunku do powyzszego kodu otwarte pytania numer 2 i 3.
  • #7
    elektryk
    Level 42  
    A można wiedzieć w jakim celu kolega to robi? RSA challange?

    Co do dużych tablic to ja bym zrobił następujące 'obejście', 2 procedury put i get które będą obsługiwać pamięć w której będzie przydzielone powiedzmy 100 takich tablic. Reszta z dzielenia numeru elementu przez 8000000 oznacza numer elementu w danej tablicu a wynik z dzielenia całkowitego numeru elementu przez 8000000 numer tablicy.
  • #8
    cortez_
    Level 26  
    Nie, dla treningu, ucze sie C i pomyslalem sobie ze to ciekawy temat, tyle sie o tym mowi to sie pobawie ;)

    Masz na mysli cos a la stronnicowanie? Moze to jest jakies wyjscie, ale kazda taka procedura spowalnia kod. Jest jeszcze jedna wlasnosc o ktore wlasnie mysle, otoz kazda liczba pierwsza oprocz 2 jest nieparzysta wiec wystarczy w tablicy pamietac tylko liczby nieparzyste i przeliczac indeksy na liczby wg wzoru 2x+1 - tez nad tym siade i zobacze jak to zrobic, to by podwoilo przestrzen poszukiwan.

    No ale pytanie dotyczylo raczej tego na co pozwala kompilator i jak sobie z tym radza ludzie wiec dziekuje za podpowiedz ;)

    PS. Z moich dowiadczen na szybko stwierdzilem ze ten program po skompilowaniu z wprowadzona poprawka na tej tablicy (mniejszy kod) wydaje sie byc o 1-2% szybszy, mozliwe to jest?
  • #9
    Gavian
    Level 14  
    Jesli chodzi o optymalizacje to radziłbym unikać takich rzeczy:
    Code:

       j =2;
       while (licznik*j<=granica2) //wszystkie jej wielokrotnosci skreslamy
       {
          lista[licznik*j]=1; //zaznaczamy ze nie sa pierwsze
          ++j;
       }
    Po co 2 razy liczyć licznik*j. Mnożenie jest jedną z najbardziej czasichłonnych operacji dla procesora (bodajrze ok. 200 taktów zegara) wiec proponuje
    Code:

     // "temp" - nasza zmnienna na przechowywanie iloczynu liczba*j
       j = 1;
       while ((temp = licznik*(++j)) <=granica2)
             lista[temp]=1; //zaznaczamy ze nie sa pierwsze

    powinno to troche przyspieszyc wykonywanie programu.
  • #10
    cortez_
    Level 26  
    rzeczywiscie minimalnie przyspieszylo, o okolo 0,5%, ale tylko gdy stosowana jest preinkrementacja (tak jak podales) a nie postinkremetacja.
  • #11
    Gavian
    Level 14  
    Nie wiem czy o to chodzi, ale program z zadanego zakresu znajduje wszystkie pierwsze liczby, a potem szuka wszytkich liczb które sa iloczynem 2 liczb pierwszych, jesli o to chodzi to ja mam taka propozycje:
    Code:

    #include <stdio.h>
    #include <conio.h>
    #include <dos.h>
    #define tabsize 1000

    int Znajdz_pierwsze(int[], int[],int);
    int Rozloz_na_pierwsze(int[], int [], int );

    void main(void){
    int tablica[tabsize*tabsize];
    int tablica2[tabsize];
    unsigned int i, j, IloscPierwszych, zakres;

    struct  time czas1, czas2;
    clrscr();
     printf("Podaj zakres : ");
     do{
       scanf("%d",&zakres);
     } while ((zakres>tabsize)||(zakres<3));
     gettime(&czas1);
       IloscPierwszych = Znajdz_pierwsze(tablica, tablica2, zakres);// szuka    pierwszych
       j = Rozloz_na_pierwsze(tablica2, tablica,IloscPierwszych);//szuka liczb
             //ktore daja sie rozlozyc na czynniki pierwsze
     gettime(&czas2);

       for (i=0; i<j; i++)
        printf("Liczba %d\n",tablica[i]);
       printf("\n%02d:%02d:%02d\n",czas1.ti_min, czas1.ti_sec, czas1.ti_hund);
       printf("%02d:%02d:%02d\n",czas2.ti_min, czas2.ti_sec, czas2.ti_hund);
       getch();
       for (i=0; i< IloscPierwszych; i++)
        printf("Liczba %d\n",tablica2[i]);
       getch();
    }
    //**********************************
    //*******    BLOK FUNKCJI    *******
    //**********************************

    int Znajdz_pierwsze(int tablica[], int tablica2[], int zakres){
    unsigned int i, s, k;
       for (i=0 ; i<=zakres; tablica[i]=0, i++);  // zeruje tablice
          for (i=2, s=0; i<=zakres; i++){
          if (tablica[i]) //jesli tablica[1]=1 to nie pierwsza
        continue;    //i pobierz nastepna
          else
        for (k=i, tablica2[s++] = i; (k+=i)<=tabsize; tablica[k] = 1);//usun wielokrotnisci
          }  //przy okazkji zapisz pierwsze do osobnej tablicy
       return s;// zwroc ilosc liczb pierwszych
    }

    int Rozloz_na_pierwsze(int tablica2[], int tablica[], int IloscPierwszych){
    unsigned int i,j,k,s;
       for (i=j=0 ; i<IloscPierwszych; i++)
          for(k=i+1; k<IloscPierwszych; k++, j++)
        tablica[j] = tablica2[i]*tablica2[k];
       return j;
    }

    Kompilowałem pod Borland C 3.0 , i nie chciało mi sie alokowac tablic dynamicznbie. Ale z przerobieniem tego programu na tablice dynamiczne nie bedzie chyba probremu. Myśle że jest dość jasno napisane.

    Pozdrawiam.
  • #12
    cortez_
    Level 26  
    to jest dokladnie to o czym wczoraj pomyslalem ;) Pobawie sie jeszcze tym kodem, pozdrawiam, dzieki ;)
  • #13
    cortez_
    Level 26  
    Przepisalem swoj program mniej wiecej wg tego algorytmu, troche innaczej, ale niewiele sie rozni. Wyszlo mi na to ze jest okolo 120 razy szybszy! ;)
  • #14
    Gavian
    Level 14  
    Witam. Sorry ale do programu wkradł sie mały błedzik. Procedura :
    Code:

    int Znajdz_pierwsze(int tablica[], int tablica2[], int zakres){
    unsigned int i, s, k;
       for (i=0 ; i<=zakres; tablica[i]=0, i++);  // zeruje tablice
          for (i=2, s=0; i<=zakres; i++){
          if (tablica[i]) //jesli tablica[1]=1 to nie pierwsza
        continue;    //i pobierz nastepna
          else
        for (k=i, tablica2[s++] = i; (k+=i)<=tabsize; tablica[k] = 1);//Tu jest bład
          }  //przy okazkji zapisz pierwsze do osobnej tablicy
       return s;// zwroc ilosc liczb pierwszych
    }
    Powinna wyglądać tak :
    Code:
    int Znajdz_pierwsze(int tablica[], int tablica2[], int zakres){ 
    
    unsigned int i, s, k;
       for (i=0 ; i<=zakres; tablica[i]=0, i++);  // zeruje tablice
          for (i=2, s=0; i<=zakres; i++){
          if (tablica[i]) //jesli tablica[1]=1 to nie pierwsza
        continue;    //i pobierz nastepna
          else
        for (k=i, tablica2[s++] = i; (k+=i)<=zakres; tablica[k] = 1);//tu jest błąd
          }  //przy okazkji zapisz pierwsze do osobnej tablicy
       return s;// zwroc ilosc liczb pierwszych
    }
    Przy niekozystnych warunkach :) Może sie wykaszaniać.
    Pozdawiam
  • #15
    cortez_
    Level 26  
    racja, ale nie korzystalemz tej procedury, zostawilem swoja, dziala wg. tego samego algorytmu.
    Temat optymalizacji uwazam za zamkniety, chyba ze ktos mnie zadziwi jeszcze sztuczkami ktore moznaby zastosowac w pierwotnym kodzie.

    Pozostaje otwarte pytanie nr 3, czyli maksymalny rozmiar tablicy jaki mozna zadeklarowac.

    W zasadzie powinno byc ono sformulowane innaczej:
    Maksymalny rozmiar tablicy z moich doswiadczen wynosi 8Mb (8mln komorek tablicy z jednobajtowa komorka albo 2lmln tablicy struktur czterobajtowych)
    Poniewaz potrzebuje liczyc rozklady wieksze lub rowne granicy 8mln to chcialbym wiedziec jak ten problem rozwiazac oprocz tej propozycji ktora podal elektryk. Moze ktos wie?