Реализовать сортировку массива: в начало поместить все простые числа, а затем все остальные

#include "stdafx.h"
#include <iostream>
using namespace std;
 
 bool Check(int n)
        {
    for (int i = 2; i < n; i++)
        if (n%i == 0)
            return false;
    return true;
 
    }
int main()
{
    int n = 0;
    cout << "Vvedite razmer massiva: ";
    cin >> n;
    int arr[100];
    int KolichestvoProstyh = 0;
    int KolichestvoNaturalnyh = 0;
    for (int i = 0; i < n; i++)
    {
        cout << "Vvedite elementy massiva: ";
        cin >> arr[i];
        if (Check(arr[i])) {
            arr[KolichestvoProstyh] = arr[i];
            KolichestvoProstyh++;
        }
        else {
            arr[KolichestvoNaturalnyh] = arr[i];
            KolichestvoNaturalnyh++;
        }
            
    }
    for (int i = 0; i < KolichestvoProstyh; i++) {
        arr[i] = arr[KolichestvoProstyh];
    }
    for (int i = KolichestvoProstyh; i < n; i++) {
        arr[i] = arr[KolichestvoNaturalnyh];
    }
    for (int i = 0; i < n; i++) {
        cout << arr[i];
    }
    system("pause");
    return 0;
}

int *arr;
arr = new int[n];