Guest User

cpp program

a guest
Apr 22nd, 2017
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <math.h>
  4. #include <new>
  5.  
  6. using namespace std;
  7.  
  8. struct Prim //struktura z jedna liczba
  9. {
  10.     int x; //wartosc podanej liczby
  11.     bool status; //status: true - liczba pierwsza, false - nie liczba pierwsza
  12.     Prim *next; //wskaznik na nastêpny element listy
  13. };
  14.  
  15.  
  16. int main()
  17. {
  18.     int n,i,j,maxi;
  19.     Prim *head = NULL; //deklaracja glowy i nadanie jej adresu zerowego
  20.     Prim *tail = NULL; //deklaracja ogona i nadanie jej adresu zerowego
  21.     Prim *nowy;
  22.  
  23.     cout<<"Podaj zakres liczb ";
  24.     cin>>n;
  25.  
  26.     for(i=2; i<=n; i++) //tworzy liste
  27.     {
  28.         nowy=new Prim; //tworzenie nowego obiektu typu prim
  29.  
  30.         nowy->next=NULL; //nastepny element wskazuje na NULL
  31.         nowy->x=i; //nadanie wartosci liczby takiej jaka jest w danej iteracji
  32.         nowy->status=true; //domyslnie kazda liczba ma status true
  33.  
  34.         if(head==NULL)//sprawdza czy zostal juz utworzony pierwszy element listy
  35.         {
  36.             head=nowy; //glowa przyjmuje adres pierwszego elementu
  37.             tail=head; //ogon tez wskazuje na pierwszy element, bo to jest pierwszy element listy
  38.         }
  39.         else
  40.         {
  41.             tail->next=nowy; //jesli lista zawiera juz pierwszy element, ogonowi dajemy wskaznik nastepnego elementu
  42.             tail=nowy;
  43.         }
  44.     }
  45.  
  46.     maxi=sqrt(n); //tworzenie warunku stopu, czyli do jakiej liczby ma sie wykonywac algorytm sita
  47.  
  48.     for(i=2; i<=maxi; i++) //iteracja wykonuje się tylko dla wielokrotnosci liczb  nie wiekszych od maxi
  49.     {
  50.         if(head->x==i)
  51.            
  52.         {
  53.             j=i+i;
  54.            
  55.             while(j<=n)
  56.             {
  57.  
  58.                 if(head->x==j)
  59.                 {
  60.                     head->status=false;
  61.                     head=head->next;
  62.                     j+=i;
  63.                 }
  64.                 else
  65.                 {
  66.                     head=head->next;
  67.                     j+=i;
  68.                 }
  69.             }
  70.         }
  71.     }
  72.  
  73.     Prim *temp=head; //poczatek wyswietlania elementow listy
  74.     while(temp!=NULL)
  75.     {
  76.         if(temp->status=true)
  77.             cout<<temp->x<<endl;
  78.         temp=temp->next;
  79.  
  80.     }
  81.  
  82.     return 0;
  83. }
Advertisement
Add Comment
Please, Sign In to add comment