Return to Revisions

Your Solve() method looks too complex to me. My (approximate) equivalent looks like:

public int Solve() {

    // 2 * 3 * 5 * 7 = 210.
    for (int i = 210; true; ++i) {
        if (FacCount(i) == 4 &&
            FacCount(i + 1) == 4 &&
            FacCount(i + 2) == 4 &&
            FacCount(i + 3) == 4) {
              return i;
        }
    }
}

Obviously, most of the work is done in FacCount(), which counts the number of distinct prime factors in its parameter:

private int FacCount(int num) {

    int fCount = 0;
    int limit = Isqrt(num);  // Integer square root.

    // Remove factors of 2
    if (num % 2 == 0) {
        ++fCount;
        do {
            num /= 2;
        } while (num % 2 == 0);

        // Reset limit.
        limit = Isqrt(num);
    }

    // Remove other (odd) factors.
    int trialFactor = 3;
    while (trialFactor <= limit) {
        if (num % trialFactor == 0) {
            ++fCount;
            do {
                num /= trialFactor;
            } while (num % trialFactor == 0);
            limit = Isqrt(num);
        }
        trialFactor += 2;
    }

    if (num > 1) { ++fCount; } // Count last factor

    return fCount;

} // end FacCount()

This will run faster if you have a NextPrime() method in your library, based on the Sieve of Eratosthenes. That will avoid having to check odd non-prime trial factors. My Java version runs in about 200 ms using the sieve to pick primes.

There is one helper method, which finds the integer square root. This version uses Newton-Raphson and is taken from CodeCodex.

public int Isqrt(int num) {
    if (0 == num) { return 0; }  // Avoid zero divide
    int n = (num / 2) + 1;       // Initial estimate, never low
    int n1 = (n + (num / n)) / 2;
    while (n1 < n) {
        n = n1;
        n1 = (n + (num / n)) / 2;
    } // end while
    return n;
} // end Isqrt()

My original code was Java, so I may have made a few mistakes in converting it to C#. Check things carefully.