Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdlib>
- #include <math.h>
- #include <new>
- using namespace std;
- struct Prim //struktura z jedna liczba
- {
- int x; //wartosc podanej liczby
- bool status; //status: true - liczba pierwsza, false - nie liczba pierwsza
- Prim *next; //wskaznik na nastêpny element listy
- };
- int main()
- {
- int n,i,j,maxi;
- Prim *head = NULL; //deklaracja glowy i nadanie jej adresu zerowego
- Prim *tail = NULL; //deklaracja ogona i nadanie jej adresu zerowego
- Prim *nowy;
- cout<<"Podaj zakres liczb ";
- cin>>n;
- for(i=2; i<=n; i++) //tworzy liste
- {
- nowy=new Prim; //tworzenie nowego obiektu typu prim
- nowy->next=NULL; //nastepny element wskazuje na NULL
- nowy->x=i; //nadanie wartosci liczby takiej jaka jest w danej iteracji
- nowy->status=true; //domyslnie kazda liczba ma status true
- if(head==NULL)//sprawdza czy zostal juz utworzony pierwszy element listy
- {
- head=nowy; //glowa przyjmuje adres pierwszego elementu
- tail=head; //ogon tez wskazuje na pierwszy element, bo to jest pierwszy element listy
- }
- else
- {
- tail->next=nowy; //jesli lista zawiera juz pierwszy element, ogonowi dajemy wskaznik nastepnego elementu
- tail=nowy;
- }
- }
- maxi=sqrt(n); //tworzenie warunku stopu, czyli do jakiej liczby ma sie wykonywac algorytm sita
- for(i=2; i<=maxi; i++) //iteracja wykonuje się tylko dla wielokrotnosci liczb nie wiekszych od maxi
- {
- if(head->x==i)
- {
- j=i+i;
- while(j<=n)
- {
- if(head->x==j)
- {
- head->status=false;
- head=head->next;
- j+=i;
- }
- else
- {
- head=head->next;
- j+=i;
- }
- }
- }
- }
- Prim *temp=head; //poczatek wyswietlania elementow listy
- while(temp!=NULL)
- {
- if(temp->status=true)
- cout<<temp->x<<endl;
- temp=temp->next;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment