Problem #124 wants us to:

The radical of n, rad(n), is the product of distinct prime factors of n. For example, \(504 = 2^3 × 3^2 × 7\), so rad(504) = 2 × 3 × 7 = 42.

Let E(k) be the kth element in the sorted n column; for example, E(4) = 8 and E(6) = 9.

If rad(n) is sorted for 1 ≤ n ≤ 100000, find E(10000).

This problem is exceedingly easy once we calculate the radicals for the numbers 1-100000. Just create a simple class to remember the n, and rad values and populate those fields and the problem is 9/10ths of the way solved. From here we can use the power of Linq, which I’m liking more and more as time goes on, and do an OrderBy on the rad values. Now this seems like it would be insufficient to solve the problem because if the radical values are the same we need to sort by the n value. Well Linq has us covered; simply add a ThenBy after the OrderBy and you can sort by a second value. This means that the overwhelming majority of the code in the solution is prime number generation, finding distinct factors, and calculation of the radicals.

A second solution without linq would be to sort by the radical value and get the radical value of the 10000th item. Then find the index of the first number with that radical and store it. Then get a list of only the numbers with that radical and sort this new list by the n value. Using the previously stored index you can then calculate what item in the new list should be the answer. But this is alot more complicated than a simple Linq expression.

A third method would be to write a custom IComparer for the class that holds the radical + n values. But this is a lot more work than is needed and would make the solution much less readable in my opinion. Besides an up to date .Net implementation (Microsoft.Net or Mono) should have Linq available.

Solution below written in c#/mono and requires Linq and .Net 4. Runs in ~5 seconds.

using System;
using System.Collections.Generic;
using System.Linq;

namespace Problem124
{
	class MainClass
	{
		class N
		{
			public ulong n = 0;
			public ulong rad = 0;

			public N (ulong num)
			{
				this.n = num;
				this.rad = rad(num);
			}
		}
		public static ulong max = 100000;
		public static List<ulong> primes = GeneratePrimes(max);
		
		
		public static void Main (string[] args)
		{
			List<N> NCases = new List<N>();
			for (ulong n = 1; n<=max;n++)
			{
				NCases.Add(new N(n));
			}
			N answer = NCases.OrderBy(x => x.rad)
				.ThenBy(x => x.n).ToList()[10000-1];
			
			Console.WriteLine(answer.n);
		}
		public static ulong rad(ulong n)
		{
			List<ulong> factors = DistinctFactors(n);
			ulong rad = 1;
			foreach(ulong f in factors)
				rad *= f;
			return rad;
		}
		public static List<ulong> DistinctFactors (ulong n)
		{
			List<ulong> factors = new List<ulong>();
			
			if(primes.Contains(n))
			{
				factors.Add(n);
				return factors;
			}
			ulong sqrt = (ulong)Math.Sqrt((double)n);
			foreach (ulong p in primes)
			{
				if (p > sqrt)
					break;
				if (n%p == 0)
				{
					factors.Add(p);
					while (n%p == 0)
						n = n/p;
				}
			}
			if (n!= 1ul)
				factors.Add(n);
			return factors;
		}
		static List<ulong> GeneratePrimes(ulong num)
		{
			List<ulong> RetValue = new List<ulong>();
			RetValue.Add((ulong)2);
			RetValue.Add((ulong)3);
			ulong Stepper = 5;
			ulong Check = 1;
			while (Stepper <= num)
			{
				foreach (ulong i in RetValue)
				{
					if (Stepper % i == 0)
					{
						Check = 0;
						break;
					}
					if (Math.Sqrt(Stepper) <= i)
					{
						break;
					}
				}
				if (Check == 1)
				{
					RetValue.Add(Stepper);
				}
				Check = 1;
				Stepper++;
				Stepper++;
			}
			return RetValue;
		}
	}
}