Здравствуйте, Sashka!
Для этого можно в процессе сортировки определять - простое ли текущее число. Но это займет немало вычислительных ресурсов, т.к. алгоритмы сортировки очень часто обращаются к элементам массива, а алгоритм определения простое число или нет не такой уж и быстрый. Чтобы избежать этого, можно завести массив типа bool, содержащий флаг того, что число простое. Этот массив можно заполнить за один проход по исходному массиву. Все остальное проблем не представляет - это обычный алгоритм сортировки выбором с пропуском непростых чисел.

Приложение:
#include <time.h>#include <cstdlib>#include <iostream>using namespace std;bool is_simple_number(int number) { if(number <= 1) return false; if(number%2 == 0) return false; int divisor = number/2; while(divisor > 2) if(number%divisor-- == 0) return false; return true;}int main(int argc, char* argv[]) { const int n = 10; int array[n]; bool is_simple[n]; srand((unsigned) time(NULL)); for(int i=0; i<n; i++) { array[i] = rand()%10; is_simple[i] = (is_simple_number(array[i])) ? true : false; } cout << "Initial array:" << endl; for(int i=0; i<n; i++) { cout << "array[" << i << "] = " << array[i]; cout << ((is_simple[i] == true) ? " - is simple" : " - is not simple") << endl; } for(int i=0; i<n-1; i++) { if(is_simple[i] == false) continue; int min = i; for(int j=i+1; j<n; j++) { if(is_simple[j] == false) continue; if(array[j] < array[min]) min = j; } if(min != i) { int temp = array[i]; array[i] = array[min]; array[min] = temp; } } cout << endl << "Array with sorted simple elements:" << endl; for(int i=0; i<n; i++) { cout << "array[" << i << "] = " << array[i]; cout << ((is_simple[i] == true) ? " - is simple" : " - is not simple") << endl; } return 0;}