# include < iostream >
# include < fstream >
# include < cmath >
using namespace std ;
struct Node {
int data;
Node * next ;
};
bool isPrime ( int num) {
if (num < 2 ) {
return false ;
}
int limit = sqrt (num);
for ( int i = 2 ; i <= limit ; i++) {
if (num % i == 0 ) {
return false ;
}
}
return true ;
}
void insertPrimes ( Node * & head ) {
Node * curr = head ;
while ( curr != NULL ) {
int num = curr ->data;
if (num < 2 ) {
curr = curr -> next ;
continue ;
}
Node * temp = curr -> next ;
curr -> next = new Node ;
curr -> next ->data = 2 ;
curr -> next -> next = new Node ;
curr -> next -> next ->data = 3 ;
Node * prev = curr -> next -> next ;
int i = 5 ;
while (i <= num) {
if ( isPrime (i)) {
prev -> next = new Node ;
prev -> next ->data = i;
prev -> next -> next = NULL ;
prev = prev -> next ;
}
i += 2 ;
}
prev -> next = temp ;
curr = prev -> next ;
}
}
void printList ( Node * head ) {
Node * curr = head ;
while ( curr != NULL ) {
cout << curr ->data << " " ;
curr = curr -> next ;
}
cout << endl ;
}
int main () {
Node * head = NULL ;
ifstream fin ( "input.txt" ) ;
int num;
while (fin >> num) {
Node * newNode = new Node ;
newNode ->data = num;
newNode -> next = head ;
head = newNode ;
}
fin. close ();
insertPrimes ( head );
printList ( head );
return 0 ;
}