# include < iostream >
# include < fstream >
# include < cmath >
using namespace std ;
struct Node {
int data;
Node * next ;
};
Node * createNode ( int val) {
Node * newNode = new Node ();
newNode ->data = val;
newNode -> next = NULL ;
return newNode ;
}
void insert ( Node ** headRef , int val) {
Node * newNode = createNode (val);
if (* headRef == NULL ) {
* headRef = newNode ;
} else {
Node * temp = * headRef ;
while ( temp -> next != NULL ) {
temp = temp -> next ;
}
temp -> next = newNode ;
}
}
bool isPrime ( int num) {
if (num < 2 ) {
return false ;
}
for ( int i = 2 ; i <= sqrt (num); i++) {
if (num % i == 0 ) {
return false ;
}
}
return true ;
}
int countDivisors ( int num) {
int count = 0 ;
for ( int i = 2 ; i <= sqrt (num); i++) {
if (num % i == 0 ) {
count ++;
}
}
return 2 * count ;
}
bool hasTwoIdenticalDigits ( int num) {
int lastDigit = num % 10 ;
int temp = num / 10 ;
while ( temp > 0 ) {
int digit = temp % 10 ;
if (digit == lastDigit ) {
return true ;
}
lastDigit = digit;
temp = temp / 10 ;
}
return false ;
}
void processList ( Node ** headRef ) {
Node * temp = * headRef ;
Node * prev = NULL ;
while ( temp != NULL ) {
if ( isPrime ( temp ->data)) {
cout << "Prime number : " << temp ->data << endl ;
if ( prev == NULL ) {
* headRef = temp -> next ;
} else {
prev -> next = temp -> next ;
}
Node * toDelete = temp ;
temp = temp -> next ;
delete toDelete ;
} else if ( countDivisors ( temp ->data) > 2 ) {
int num = temp ->data;
Node * newNode = NULL ;
while (num > 1 ) {
for ( int i = 2 ; i <= sqrt (num); i++) {
if (num % i == 0 ) {
if ( newNode == NULL ) {
newNode = createNode (i);
} else {
insert (& newNode , i);
}
num = num / i;
break ;
}
}
}
if ( newNode != NULL ) {
newNode -> next = temp ;
if ( prev == NULL ) {
* headRef = newNode ;
} else {
prev -> next = newNode ;
}
prev = newNode ;
} else {
prev = temp ;
}
temp = temp -> next ;
} else if ( hasTwoIdenticalDigits ( temp ->data)) {
if ( prev == NULL ) {
* headRef = temp -> next ;
} else {
prev -> next = temp -> next ;
}
Node * toDelete = temp ;
temp = temp -> next ;
delete toDelete ;
} else {
prev = temp ;
temp = temp -> next ;
}
}
}
void printList ( Node * head ) {
Node * temp = head ;
while ( temp != NULL) { cout << temp ->data << " "; temp = temp -> next ; } cout << endl ; }
int main () { ifstream fin("input.txt"); Node * list = NULL; int val; while (fin >> val) { insert(& list , val); } fin.close ();
cout << "Original list : " ;
printList ( list );
processList (& list );
cout << " Processed list : " ;
printList ( list );
return 0 ;
}