Project Euler #47: Distinct primes factors

Question

I have solved Project Euler's problem number 47, which reads:

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 prime factors each. What is the first of these numbers?

The correct answer is :

134043.

I used some sort of memoization to work out the problem but the performance is still pretty bad: 5.4–5.5 seconds. The trick in this question here is that the prime factors can actually be on some power which if evaluated doesn't result in a prime number but if the base is prime it's fine: e.g., 2² = 4.

Here is my solution:

public class Problem47 : IProblem
{
    public int ID => 47;
    public string Condition => ProblemsConditions.ProblemConditions[ID];

    //Key - value to power
    //Value - factorized value
    private readonly Dictionary<int, bool> passedNumbers = new Dictionary<int, bool>();
    private readonly Dictionary<int, int> factorizedPowers = new Dictionary<int, int>();
    private readonly HashSet<int> primes = new HashSet<int>();

    private const int primeFactorCount = 4;

    public ProblemOutput Solve()
    {
        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 2 * 3 * 5 * 7; ; i++)
        {
            int[] numbers =
            {
                i, i + 1, i + 2, i + 3
            };
            int skipAmount = 0;
            foreach (int n in numbers)
            {
                bool value;
                if (passedNumbers.TryGetValue(n, out value))
                {
                    if (!value)
                    {
                        skipAmount = n - (i - 1);
                    }
                }
                else
                {
                    passedNumbers.Add(n, HasNPrimeFactors(n, primeFactorCount));
                    if (!passedNumbers[n])
                    {
                        skipAmount = n - (i - 1);
                    }
                }
            }
            if (skipAmount != 0)
            {
                i += skipAmount - 1;
                continue;
            }
            sw.Stop();
            return new ProblemOutput(sw.ElapsedMilliseconds, numbers[numbers.Length - primeFactorCount].ToString());
        }
    }

    private bool HasNPrimeFactors(int input, int n)
    {
        Dictionary<int, int> factors = new Dictionary<int, int>();
        for (int i = 2; input > 1 ; i++)
        {
            if (input % i == 0)
            {
                if (primes.Contains(i) || IsPrime(i))
                {
                    if (!primes.Contains(i))
                    {
                        primes.Add(i);
                    }
                    if (factorizedPowers.ContainsValue(i))
                    {
                        int maximizedPower = GetMaximizedFactor(input, i);
                        input /= maximizedPower;
                        if (factors.ContainsKey(i))
                        {
                            factors[i] += GetPowerOfValue(maximizedPower, i);
                        }
                        else
                        {
                            factors.Add(i, GetPowerOfValue(maximizedPower, i));
                        }
                    }
                    else
                    {
                        input /= i;
                        if (factors.ContainsKey(i))
                        {
                            factors[i]++;
                            factorizedPowers.Add((int) Math.Pow(i, factors[i]), i);
                        }
                        else
                        {
                            factors.Add(i, 1);
                        }
                    }
                }
            }
            if (i > input)
            {
                i = 1;
            }
        }
        return factors.Count == n;
    }

    private int GetMaximizedFactor(int input, int value)
    {
        var matches = factorizedPowers.Where(x => x.Value == value && input % x.Key == 0);
        return matches.Any() ? matches.Max().Key : value;
    }

    private static int GetPowerOfValue(int input, int value)
    {
        int count = 0;
        while (input > 1)
        {
            input /= value;
            count++;
        }
        return count;
    }

    private bool IsPrime(int value)
    {
        if (value < 2) { return false; }
        if (value % 2 == 0) { return value == 2; }
        if (value % 3 == 0) { return value == 3; }
        if (value % 5 == 0) { return value == 5; }
        if (value == 7) { return true; }

        for (int divisor = 7; divisor * divisor <= value; divisor += 30)
        {
            if (value % divisor == 0) { return false; }
            if (value % (divisor + 4) == 0) { return false; }
            if (value % (divisor + 6) == 0) { return false; }
            if (value % (divisor + 10) == 0) { return false; }
            if (value % (divisor + 12) == 0) { return false; }
            if (value % (divisor + 16) == 0) { return false; }
            if (value % (divisor + 22) == 0) { return false; }
            if (value % (divisor + 24) == 0) { return false; }
        }
        return true;
    }
}

Please ignore the inheritance, the ID and Condition properties, and the ProblemOutput class. Those are irrelevant for this question and have no effect on the program whatsoever.

Answer 1

If you're working through the Project Euler questions, you should become familiar with the Seive of Eratoshenes.

Not only is it a very simple way to generate a bunch of prime numbers at once, but it's an algorithm which can be subtly modified to solve other problems.

In this problem, we want to calculate how many prime factors each number in a range has. We've going to be testing a lot of numbers, so it would be great if we can calculate all of the factor counts at once. And we can!

First, pick a safe top number that we're going to test up to. I'll guess that the answer will be a number less than a million.

Create an array of a million zeros.

It starts as an array of zeros, but we want to transform this array so that:

array[i] == count_of_factors(i)

• Start at 2. array[2] == 0, so therefore 2 is prime. Now we can add 1 to {array[4], array[6], array[8] ... array[999998]}, because they are factors of 2.
• Move to 3. array[3] == 0, so add 1 to {array[6], array[9], array[12] ... array[999999]}
• Move to 4. array[4] == 1. (We've already incremented it) Because it is not 0, we know it is not a prime number, so we ignore it.
• Move to 5. array[5] == 0, so add 1 to {array[10], array[15], array[20], array[25]...array[999995]

And so on. When you're done, every number will either be 0 (if the index is prime), or it will be the count of prime factors of that index. Now it's as simple as finding the first four contiguous fours.

This solution takes around 130 milliseconds:

static int SolveProblem()
{
   int[] factorCounts = new int[1000000];
   for(int i = 2; i < factorCounts.Length; ++i)
   {
      if(factorCounts[i] == 0) // It's Prime
      {
         for(int j = i*2; j < factorCounts.Length; j+=i)
         {
            ++factorCounts[j];
         }
      }
   }

   // Now find the first four contiguous fours
   int contiguousFours = 0;
   for (int i = 210; i < factorCounts.Length; ++i)
   {
      contiguousFours = factorCounts[i] == 4 ? contiguousFours + 1 : 0;
      if(contiguousFours == 4)
      {
         return i - 3;
      }
    }
    return -1;
}

But we can do better than this. The above code has two loops: one which calculates the factor counts and one which searches for the contiguous fours. Lets merge this into one loop: that way it will stop generating factor counts as soon as it finds the fours.

static int SolveProblem()
{
    int[] factorCounts = new int[1000000];
    int contiguousFours = 0;
    for(int i = 2; i < factorCounts.Length; ++i)
    {
        contiguousFours = factorCounts[i] == 4 ? contiguousFours + 1 : 0;
        if (contiguousFours == 4)
        {
            return i - 3;
        }
        if (factorCounts[i] == 0) // It's Prime
        {
            for(int j = i*2; j < factorCounts.Length; j+=i)
            {
                ++factorCounts[j];
            }
        }
    }
    return -1;
}

Now we're down to 85 milliseconds.

Answer 2

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.

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.

Answer 3

    for (int i = 2 * 3 * 5 * 7; ; i++)
    {
        int[] numbers =
        {
            i, i + 1, i + 2, i + 3
        };
        int skipAmount = 0;  

        ...
        ...
        if (skipAmount != 0)
        {
            i += skipAmount - 1;
            continue;
        }

Only a quick note

You are using skipAmount as a flag and to increment the loop counter here. By using a boolean as a flag and just increment the loop counter by 3 you will get the same effect.

Now more of meat

You can speed up your implementation by reversing the numbers array to first check i + 3. If this doesn't has the desired number of prime factors you won't need to check the remaining items in the array any more.

This will result (using poor man benchmarking) in around 2200ms, which isn't anything like @rossum's answer.

Another advantage is that you won't need passedNumbers any more. The loop will boil down to

for (int i = 2 * 3 * 5 * 7; ; i++)
{
    int[] numbers =
    {
        i + 3, i + 2, i + 1, i 
    };

    bool hasFinished = true;

    foreach (int n in numbers)
    {

        if (!HasNPrimeFactors(n, primeFactorCount))
        {
            hasFinished = false;
            break;
        }
    }
    if (hasFinished)
    {
        return numbers[3].ToString();
    }
}  

which as a side effect looks much nicer.

---

HasNPrimeFactors()

    Dictionary<int, int> factors = new Dictionary<int, int>();
    for (int i = 2; input > 1 ; i++)
    {
        if (input % i == 0)
        {
            if (primes.Contains(i) || IsPrime(i))
            {
                if (!primes.Contains(i))
                {
                    primes.Add(i);
                }  

The second call to primes.Contains(i) can be omitted because the Add() method of a HashSet<T> does almost do the same checks than Contains() but by checking first if !Contains() will do this twice.

Reference Source: AddIfNotPresent() and Contains() please note that Add() just calls AddIfNotPresent()

---

                if (factorizedPowers.ContainsValue(i))
                {
                    int maximizedPower = GetMaximizedFactor(input, i);
                    input /= maximizedPower;
                    if (factors.ContainsKey(i))
                    {
                        factors[i] += GetPowerOfValue(maximizedPower, i);
                    }
                    else
                    {
                        factors.Add(i, GetPowerOfValue(maximizedPower, i));
                    }
                }
                else
                {
                    input /= i;
                    if (factors.ContainsKey(i))
                    {
                        factors[i]++;
                        factorizedPowers.Add((int) Math.Pow(i, factors[i]), i);
                    }
                    else
                    {
                        factors.Add(i, 1);
                    }
                }

Here you have some code duplication which can be removed by

• storing the calculated GetPowerOfValue(maximizedPower, i)); into a variable.
• instead of calling first ContainsKey() you should use TryGetValue() just before the if.

The HasNPrimeFactors() method could then look like

private bool HasNPrimeFactors(int input, int n)
{

    Dictionary<int, int> factors = new Dictionary<int, int>();
    for (int i = 2; input > 1; i++)
    {
        if (input % i == 0)
        {
            if (primes.Contains(i) || IsPrime(i))
            {
                primes.Add(i);

                int factor;
                factors.TryGetValue(i, out factor);

                if (factorizedPowers.ContainsValue(i))
                {
                    int maximizedPower = GetMaximizedFactor(input, i);
                    factors[i] = factor + GetPowerOfValue(maximizedPower, i);

                    input /= maximizedPower;
                }
                else
                {
                    factors[i] = factor++;

                    if (factor > 1)
                    {
                        factorizedPowers.Add((int)Math.Pow(i, factor), i);
                    }

                    input /= i;
                }
            }
        }
        if (i > input)
        {
            i = 1;
        }

    }

    return factors.Count == n;
}

which now runs in ~1750 ms.

---

Just a little side note regarding the answer/solution posted by @rossum.

In its current form it runs in about ~75ms and produces the correct result. By checking the item of i +3 first like

public int Solve()
{

    // 2 * 3 * 5 * 7 = 210.

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

It only takes <50ms.