pe500.cs

// On my computer (i7-4790K 4.0GHz) the overall time is 571ms

/*
 * Simple example of algorithm:
 * For example we want to calculate the smallest number that has 2^4 factors that is 120
 * We start by calculating prime number from 2 to n; (I'm not very sure how to calculate n)
 * After I fill an sorted array named factors just by prime numbers, I start with the smallest one (2)
 * I multiply the smallest one in a variable called result with the initial value of 1
 * After I multiply smallest value from the sorted list in the result, I remove that value from list, and re-inset value ^ 2
 * This makes sure that for each number in the list that we multiply in, the number of factors are doubled.
 * Also I can call this list, `different`. Just to say that if I multiply a number in result, how much different it has on result. We sure want the smallest different
 */
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

namespace PE500
{
    class Program
    {
        static void Main()
        {
            Stopwatch stopwatch = new Stopwatch(); // just calculate how long it takes
            stopwatch.Start();
            // define factors primes
            // the whole point of the fucking question was using these type of collections
            // at first I wrote it without this. I think the compute time would be about 1.5 hours
            // also this could be called "The Difference"; By multiplying each number in this set in the result,
            // the number of factors will be multiplied by 2
            // after we get the number that has the least effect on the result (the smallest one), we must square that number
            // and store it again in this set
            // for an example, see above
            SortedSet<ulong> factors = new SortedSet<ulong>();
            // generate prime numbers
            {
                const int to = 7376497; // I tried different values starting 500500; It seems that 7376497 is the last prime used
                var p = Primes(to);
                factors.Add(2); // as explained below
                factors.Add(3);
                for (uint i = 5; i < p.Length; i += 6) // any prime number is 6k +- 1
                {
                    if(!p[(int)i])
                        factors.Add(i);
                    if(!p[(int)i + 2])
                        factors.Add(i + 2);
                }
            }
            // calculate
            ulong result = 1;
            for (int i = 0; i < 500500; i++) // you can change 500500 to any number to find the first number that has 2^n factors 
            {
                ulong f = factors.Min; // get the number that has the least effect on multiplication
                result *= f; // directly multiply the number; I do not store any powers or ...
                result %= 500500507; // you can change the mod here
                factors.Remove(f); // remove that number to change it (in sorted set, we should not change values)
                factors.Add(f * f); // re-insert the number^2 in set
            }
            stopwatch.Stop();
            Console.WriteLine(result);
            Console.WriteLine(stopwatch.Elapsed);
        }
        /// <summary>
        /// Generate primes from 1 to n, excluding 2 and 3. True means that the number is not prime
        /// </summary>
        /// <param name="to">The last prime number to check</param>
        /// <returns></returns>
        private static BitArray Primes(int to)
        {
            int length = to + 1;
            BitArray bitSet = new BitArray(length);
            int i;
            for (i = 5;; i+=4) {
                int j;
                if (!bitSet[i]) {
                    if (i * i > length)
                        break;
                    j = 2;
                    do {
                        bitSet[j*i] = true;
                        j++;
                    } while (j * i < length);
                   
                }
                i+=2;
                if (!bitSet[i]) {
                    if (i * i > length)
                        break;
                    j = 2;
                    do {
                        bitSet[j*i] = true;
                        j++;
                    } while (j * i < length);
                    
                }
            }

            return bitSet;
        }
    }
}