qsort - быстрая сортировка, хороший алгоритм, вопрос, зачтут ли его Вам.
Что делает? Сортирует массив. Требует указатель на массив, количество элементов, размер одного элемента и функцию сравнения.
Вот тут хорошо описано, как раз для Вашего случая простых чисел.
http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/
Под второй массив можно выделять и меньше. Для этого достаточно посчитать, сколько простых чисел, а потом ещё раз прогнать и скопировать. А можно выделить и столько же... Смотреть надо на объёмы данных и учитывать, что важнее - скорость обработки или экономичность по памяти.
Сортировку, наверное, лучше написать свою. Пусть медленную, хоть пузырьком, но свою. Полезно))