Skip to main content
Code Review

Return to Answer

Added ETA with revised loop.
Source Link
rossum
rossum
  • 635
  • 4
  • 13

ETA: Following @Heslacher's comments in his answer below, about stepping more than one. Yes, time can be saved, but the step is not constant. The size of step depends on the number of consecutive integers with four different factors found. The search loop could be rewritten:

    // 2 * 3 * 5 * 7 = 210.
    int step = 1;
    for (int i = 210; true; i += step) {
        if (FacCount(i) != 4) {
            step = 1;
        } else if (FacCount(i + 1) != 4) {
            step = 2;
        } else if (FacCount(i + 2) != 4) {
            step = 3;
        } else if (FacCount(i + 3) != 4) {
            step = 4;
        else {
            // Only get here with four consecutive four-counts.
            return i;
        }
    }

This avoids checking a number's factor count twice by stepping to the number after the first non-four factor count. As a disadvantage, the logic of the search is not as clear as with the original version.

ETA: Following @Heslacher's comments in his answer below, about stepping more than one. Yes, time can be saved, but the step is not constant. The size of step depends on the number of consecutive integers with four different factors found. The search loop could be rewritten:

    // 2 * 3 * 5 * 7 = 210.
    int step = 1;
    for (int i = 210; true; i += step) {
        if (FacCount(i) != 4) {
            step = 1;
        } else if (FacCount(i + 1) != 4) {
            step = 2;
        } else if (FacCount(i + 2) != 4) {
            step = 3;
        } else if (FacCount(i + 3) != 4) {
            step = 4;
        else {
            // Only get here with four consecutive four-counts.
            return i;
        }
    }

This avoids checking a number's factor count twice by stepping to the number after the first non-four factor count. As a disadvantage, the logic of the search is not as clear as with the original version.

Source Link
rossum
rossum
  • 635
  • 4
  • 13

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.