Project Euler #47: Distinct primes factors

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 = 22 × 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., 22 = 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 passedNumbers = new Dictionary();
private readonly Dictionary factorizedPowers = new Dictionary();
private readonly HashSet primes = new HashSet();

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 (!passedNumber

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.

StackExchange Code Review Q#151566, answer score: 5