From ProgSoc Wiki

Euler Problem 124

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.

If we calculate rad(n) for 1 ≤ n ≤ 10, then sort them on rad(n), and sorting on n if the radical values are equal, we get (n, rad(n)):

(1,1), (2,2), (4,2), (8,2), (3,3), (9,3), (5,5), (7,7), (10,10)

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).

Solutions to Problem 124

Python by Althalus

Runtime: 4.8 seconds

from primeFunctions import genPrimes, getFactors

ps = genPrimes(100000)

def rad(n):
    d = {}
    fs = getFactors(n,ps)
    for x in fs: 
        d[x] = x 
    fs = d.values()
    return reduce(lambda x,y: x*y, fs) 

list = [(1,1),]
for x in range(2,100001):
    list.append((rad(x),x))
list.sort()
print list[10000-1]

For reference, by genPrimes and getFactors functions are like so:

def genPrimes(n):
 #1 is not prime.
 if n < 2: return None
 #2 is the first prime.
 if n == 2: return [2] 

 # Sieve of eratosthenes (sp?)
 # get a list of odd numbers (evens aren't prime cept for 2) (don't include 1 - it's not prime)
 candidates = range(3,n,2)
 for i in xrange(int(n**0.5)):
  p = candidates[i]
  if p > 0:
   j=i+p
   while j < len(candidates):
    candidates[j] = 0 
    j+=p
 return [2]+[x for x in candidates if x > 0]

def getFactors(n,primesList):
    i = 0
    factors=[]
    while n != 1:
            while n%primesList[i] == 0:
                factors.append(primesList[i])
                n=n/primesList[i]
            i+=1
    return factors