using System;

using System.Collections.Generic;

using System.Linq;

​

namespace CallaghanDev.Fun.ProjectEuler

{

    public class Problem87

    {

        public static Problem87 obj = new Problem87();

        public static void Main() {

            obj.Run();

        }

        public void Run()

        {

            // The problem asks us to find the number of integers below fifty million that can be expressed as the sum of a prime squared, a prime cubed, and a prime to the fourth power.  We need to find all unique combinations of such sums.

​

            // First, we define the upper limit for the numbers we are considering.  This is given as 50,000,000.

            const int limit = 50000000;

​

            // To efficiently find the primes we need, we can generate all primes up to the square root of the limit. Why the square root? Because if p^2 + q^3 + r^4 < limit, then p^2 < limit, meaning p < sqrt(limit).  The largest possible prime we need to consider for the squared term is the square root of the limit.  The other prime powers will naturally be smaller.

            // We use our GeneratePrimesUnder function to achieve this. Note that we only need primes up to the square root of the limit because the smallest possible sum involves the square of a prime, and if that square alone exceeds the limit, further calculations with cubes and fourth powers are unnecessary for that prime.

            var primes = GeneratePrimesUnder(Math.Sqrt(limit));

​

            // We'll use a HashSet to store the unique numbers that satisfy the condition. A HashSet is ideal here because it automatically handles duplicate entries, ensuring we only count each valid sum once.

            HashSet<int> numbers = new HashSet<int>();

​

            // Now we need to iterate through combinations of primes to calculate the sums of their squares, cubes, and fourth powers.  We'll use nested loops to accomplish this.

​

            // The outer loop iterates through the list of primes, considering each prime for the squared term.

            for (int i = 0; i < primes.Count; i++)

            {

                // Calculate the square of the current prime.

                double primeSquare = Math.Pow(primes[i], 2);

​

                // Optimization: If the square of the current prime is already greater than or equal to the limit, no further combinations involving this prime's square will produce valid results. We can break out of the outer loop.

                if (primeSquare >= limit) break;

​

                // The second loop iterates through the list of primes again, considering each prime for the cubed term.

                for (int j = 0; j < primes.Count; j++)

                {

                    // Calculate the cube of the current prime.

                    double primeCube = Math.Pow(primes[j], 3);

​

                    // Optimization: If the sum of the current prime's square and the current prime's cube is already greater than or equal to the limit, no further combinations involving these primes' powers will produce valid results. We can break out of the second loop.

                    if (primeSquare + primeCube >= limit) break;

​

                    // The innermost loop iterates through the list of primes one last time, considering each prime for the fourth power term.

                    for (int k = 0; k < primes.Count; k++)

                    {

                        // Calculate the fourth power of the current prime.

                        double primeFourth = Math.Pow(primes[k], 4);

​

                        // Calculate the sum of the prime squared, prime cubed, and prime to the fourth power.

                        double sum = primeSquare + primeCube + primeFourth;

​

                        // Optimization: If the calculated sum is greater than or equal to the limit, this combination is invalid, and any further combinations with the current squared and cubed primes will also exceed the limit. We can break out of the innermost loop.

                        if (sum >= limit) break;

​

                        // If the sum is less than the limit, it's a potential candidate. We add the integer part of the sum to our HashSet. The cast to `int` is safe here because the primes are integers, and their powers and sum will also be integers.  The HashSet will ensure we only store unique sums.

                        numbers.Add((int)sum);

                    }

                }

            }

​

            // After iterating through all possible combinations, the HashSet 'numbers' contains all the unique integers below fifty million that can be expressed as the sum of a prime squared, a prime cubed, and a prime to the fourth power.  We output the count of elements in the HashSet, which is the answer to the problem.

            Console.WriteLine(numbers.Count);

        }

​

        // This function implements a simple sieve of Eratosthenes algorithm to generate all prime numbers under a given limit.

        List<int> GeneratePrimesUnder(double limit)

        {

            // Create a boolean array where the index represents a number, and the value indicates whether the number is prime (true) or not (false). Initially, assume all numbers are prime.

            bool[] isPrime = Enumerable.Repeat(true, (int)limit + 1).ToArray();

            // Create a list to store the prime numbers found.

            var primes = new List<int>();

​

            // Start iterating from 2, the smallest prime number, up to the given limit.

            for (int p = 2; p <= limit; p++)

            {

                // If isPrime[p] is true, it means p has not been marked as a multiple of any smaller prime, so it is a prime number.

                if (isPrime[p])

                {

                    // Add the prime number to our list of primes.

                    primes.Add(p);

​

                    // Now, mark all multiples of p (starting from 2*p) as not prime.  We start from 2*p because p*1 is p itself, which is prime.

                    for (int multiple = p * 2; multiple <= limit; multiple += p)

                    {

                        isPrime[multiple] = false;

                    }

                }

            }

            // After the loop completes, the 'primes' list contains all prime numbers under the given limit.

            return primes;

        }

    }

}