Sin haberme parado a mirar el código, para que no te tome 4 como primo tienes que mirar que 4%2 por ejemplo no te de resto 0, entonces si da 0 es que no es primo, lo que tienes que hacer es ir probando a dividirlo entre los números primos menores que él, así ves si nunca ha dado resto 0 es que es primo, por ejemplo un programa que factoriza un número:
int main() {
int n,aux=2;
cin>>n;
Factorizar(n,aux);
}
void Factorizar(int n, int aux) {
if(aux==n)
cout<<n<<endl;
else {
if(n%aux==0) {
cout<<aux<<" ";
n=n/aux;
Factorizar(n,aux);
}
else Factorizar(n,aux+1);
}
}
Le pasas como aux, el 2, que es el primer primo (quitando el 1), y ya luego la misma función va incrementandolo.