Project Euler task 41

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

---------------------------------------------------------------------------

#include < iostream >

#include < vector >

#include < memory.h >

#include < math.h >

using namespace std;

vector< int > permutations(vector< int > _v) {

vector< int > vRes;

int * piTemp = new int[_v.size()];

memset(piTemp, 0, sizeof(int) * _v.size());

for (int k = 0; k < _v.size(); k++)

piTemp[k] = k;

int iDec = 1;

int iRes = 0;

for (int k = _v.size() - 1; k >= 0; k--) {

iRes += _v[piTemp[k]] * iDec;

iDec *= 10;

}

while (1) {

int j;

// j

// |

// 0 1 2 3 4 5 6

// Find element, whose value is less than

// the value of the next element (5 < 6).

for (j = _v.size() - 1; j >= 1; j--)

if (piTemp[j] > piTemp[j - 1]) {

j--;

break;

}

// Nothing to process.

if (j < 0)

break;

// find the minimal element that is greater than piTemp[j]

int i = _v.size() - 1;

int iTempValue = -1;

for (int k = _v.size() - 1; k > j; k--)

if (piTemp[k] > piTemp[j] && (iTempValue < 0 || iTempValue > piTemp[k])) {

iTempValue = piTemp[k];

i = k;

}

if (iTempValue == -1)

break;

iTempValue = 0;

// swap (i, j)

int iTemp = piTemp[i];

piTemp[i] = piTemp[j];

piTemp[j] = iTemp;

for (int k = _v.size() - 2; k > j; k--)

if (piTemp[k] > piTemp[k + 1]) {

int iTmp = piTemp[k + 1];

piTemp[k + 1] = piTemp[k];

piTemp[k] = iTmp;

}

iDec = 1;

iRes = 0;

for (int k = _v.size() - 1; k >= 0; k--) {

iRes += _v[piTemp[k]] * iDec;

iDec *= 10;

}

vRes.push_back(iRes);

}

delete piTemp;

return vRes;

}

bool isPrime(int _iNum) {

if (_iNum <= 1 || (_iNum > 2 && _iNum % 2 == 0) || (_iNum > 5 && _iNum % 10 == 5))

return false;

for (int i = 2; i <= (int) sqrt((double) _iNum); i++)

if (_iNum % i == 0)

return false;

return true;

}

int main() {

vector vNums;

vNums.push_back(1);

vNums.push_back(2);

vNums.push_back(3);

vNums.push_back(4);

vNums.push_back(5);

vNums.push_back(6);

vNums.push_back(7);

int iMaxPrime = 0;

vector vRes = permutations(vNums);

for (int i = 0; i < vRes.size(); i++)

if (isPrime(vRes[i]))

iMaxPrime = vRes[i];

cout << iMaxPrime << endl;

return 0;

}