fork download
copy 
  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.     Prim *wsk=head; //pomocniczy wskaznik do przeszukiwania listy
  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(wsk->x==j)
  59.                 {
  60.                     wsk->status=false;
  61.                     wsk=wsk->next;
  62.                     j+=i;
  63.                 }
  64.                 else
  65.                 {
  66.                     wsk=wsk->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. }
  84.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
30
stdout
copy 
Podaj zakres liczb 2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
https://ideone.com/pyBguY
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!