//Bai 21

//Su dung mang tinh

#include <iostream>

#include <math.h>

#include<conio.h>

using namespace std;

// Lop ngan xep

class Stack

{

private:

int m[100];

int t, size;

public:

Stack():size(50),t(-1)

{ }

Stack(int kt);

void push(int a);

int pop();

int top();

int full();

int empty();

};

//-------------

int LaNguyenTo(int a);

// Ham main

int main()

{

int n,i;

do

{

cout<<"Nhap so nguyen duong n(>=50): ";

cin>>n;

} while(n<50);

Stack s(n);

for (i = 2; i < n; i++)

if(LaNguyenTo(i)) s.push(i);

cout<<"Cac so nguyen to nho hon "<<n<<" la:

";

while(!s.empty())

cout<<s.pop()<<" ";

cout<<"

Ket thuc

";

getch();

return 0;

}

// Dinh nghia cac ham cua lop ngan xep

Stack::Stack(int kt)

{

if(kt>100)

{

cout<<"Kich thuoc phai <=100!"; exit(1);

}

size = kt; t=-1;

}

void Stack::push(int a)

{

if(!full())

m[++t] = a;

else

cout<<"Ngan xep da day!";

}

int Stack::pop()

{

if(empty())

{

cout<<"Ngan xep da rong"; return -1;

}

return m[t--];

}

int Stack::top()

{

return m[t];

}

int Stack::full()

{

if (t == size-1) return 1;

else return 0;

}

int Stack::empty()

{

if (t == -1) return 1;

else return 0;

}

//--------------

int LaNguyenTo(int a)

{

int i;

for(i=2;i<=(int)sqrt(a);i++)

if(a%i==0) return 0;

return 1;

}