Решение: последовательно проверяются все возможные делители, не кратные 2. Если число делится без остатка, то оно - не простое.
В википедии присутствует более совершенный алгоритм.
#include "stdafx.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int x;
cin >> x;
bool isPrime = true;
int i;
if (x == 2) {
isPrime = true;
}
else if (x % 2 == 0) {
isPrime = false;
i = 2;
}
else {
for (i = 3; i < x; i += 2)
{
if (x % i == 0) {
isPrime = false;
break;
}
}
}
if (isPrime) {
cout << "prime" << endl;
}
else {
cout << "composite" << endl << i << endl;
}
system("pause");
return 0;
}