Project Euler task 47

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 7
15 = 3 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² 7 23
645 = 3 5 43
646 = 2 17 19.

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

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

#include < iostream >

#include < set >

using namespace std;

const int ciMax = 1000000;

const int ciSeqCount = 4;

int iEratArray[ciMax];

int main() {

memset(iEratArray, 0, ciMax);

// eratosphene's sieve

iEratArray[0] = 1;

iEratArray[1] = 1;

for (int k = 2; k < ciMax; k++) {

if (iEratArray[k]) // if not prime, continue

continue;

for (int j = 2; k * j < ciMax; j++)

iEratArray[k * j] = 1; // mark as not prime

}

int iSeq = 0;

set< int > sDivNumberSet;

for (int i = 2; i < ciMax; i++) {

sDivNumberSet.clear();

if (iSeq == ciSeqCount) { // quit if the sequence was found

cout << i - ciSeqCount << endl;

return 0;

}

int iTemp = i;

while (1) {

int iFlag = 0;

for (int j = 2; j <= i / 2; j++) {

if (iEratArray[j]) // skip non-primes

continue;

if (iTemp % j == 0) {

iTemp /= j;

sDivNumberSet.insert(j);

iFlag = 1;

break;

}

}

if ((sDivNumberSet.size() > ciSeqCount) || (iFlag == 0))

break;

}

if (sDivNumberSet.size() == ciSeqCount) {

iSeq++;

continue;

}

iSeq = 0;

}

return 0;

}