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.