2011-02-19

Project Euler Problem 124 - Solved

Comments

The statement can be found here and the solution for this problem is quite straightforward.

First get the primes below 100000, after that initialize the list of rads, for each position I store the rad and the n.
To fill in the rad list for each prime multiply the rad for all the positions of numbers that are divisible for that prime, which is pretty easy, start at the prime and make steps of size prime until the limit is reached.

After going through all the primes we have the rad list filled. We sort it and extract the position 10000 and the n is stored in the second position of the element.

The python file is problem124.py:

from CommonFunctions import find_primes_less_than

LIMIT = 100000

if __name__ == '__main__':
    primes = find_primes_less_than(LIMIT)

    rads = [[1, i] for i in range(LIMIT+1)]
    for p in primes:
        for i in range(p, LIMIT+1, p):
            rads[i][0] *= p
    print("The result is:", sorted(rads)[10000][1])
comments powered by Disqus