# include < iostream >
# include < fstream >
using namespace std ;
struct Node {
int val;
Node * prev ;
Node * next ;
};
int cmmdc ( int a, int b) {
if (b == 0 ) {
return a;
}
return cmmdc (b, a % b);
}
bool is_prime ( int n) {
if (n < 2 ) {
return false ;
}
for ( int i = 2 ; i <= n / 2 ; i++) {
if (n % i == 0 ) {
return false ;
}
}
return true ;
}
void eliminate_primes_and_insert_gcds ( Node * head ) {
Node * curr = head ;
while ( curr != NULL && curr -> next != NULL ) {
Node * next = curr -> next ;
if ( is_prime ( curr ->val)) {
// eliminate current node
if ( curr == head ) {
head = next ;
next -> prev = NULL ;
} else {
curr -> prev -> next = next ;
next -> prev = curr -> prev ;
}
delete curr ;
curr = next ;
} else {
// calculate gcd and insert it
int gcd = cmmdc ( curr ->val, next ->val);
Node * new_node = new Node { gcd , curr , next };
curr -> next = new_node ;
next -> prev = new_node ;
curr = next -> next ;
}
}
}
void print_list ( Node * head ) {
Node * curr = head ;
while ( curr != NULL ) {
cout << curr ->val << " " ;
curr = curr -> next ;
}
cout << endl ;
}
int main () {
ifstream fin ( "input.txt" ) ;
// create the linked list
Node * head = NULL ;
Node * tail = NULL ;
int num;
while (fin >> num) {
Node * new_node = new Node {num, tail , NULL };
if ( tail == NULL ) {
head = new_node ;
} else {
tail -> next = new_node ;
}
tail = new_node ;
}
fin. close ();
cout << "Original list : " ;
print_list ( head );
eliminate_primes_and_insert_gcds ( head );
cout << " Modified list : " ;
print_list ( head );
// free memory
Node * curr = head ;
while ( curr != NULL ) {
Node * next = curr -> next ;
delete curr ;
curr = next ;
}
return 0 ;
}