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

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