Solution to Riddler basic, 190111

main.py

THE_NUMBER = ('53013180176278773980288979275410970{}13935854771006625765205034'
              '6294484433323974747960297803292989236183040000000000')


def factorize(x: int) -> list:
    """ Return list of prime factors of `x` """
    last_factor = 1
    factors = []
    while True:
        last_factor = find_factor(x)

        # If `x` has no factor, it's prime; break the loop
        if last_factor < 0:
            factors.append(x)
            break

        # If the factor is prime, add it to the list
        if is_prime(last_factor):
            new_factors = [last_factor]
        # If it's not prime, it can be factorized
        else:
            new_factors = factorize(last_factor)

        # Divide out the prime factors we've found
        for f in new_factors:
            x = x // f              # If you use usual / it bumps it to a float

        factors += new_factors

    return factors


def find_factor(x: int) -> int:
    """
    Find and return any factor of `x`. If no factor can be found, return -1.
    """
    for i in range(2, 100):     # Lower the upper bound on this to speed up
        if x % i == 0:
            return i
    return -1


def is_prime(x: int) -> bool:
    """ Take integer `x`, return True if `x` is prime, else False """
    for num in range(2, int(x * 0.5)):
        if x % num == 0:
            return False
    return True


if __name__ == "__main__":
    prime_list = []
    the_numbers = []
    options = range(0, 10)
    for digit in options:
        print(f'Processing {digit}')
        this_number = int(THE_NUMBER.format(digit))
        the_numbers.append(this_number)
        this_factors = factorize(this_number)
        prime_list.append(this_factors)
    answers = list(map(max, prime_list))
    min_ans = min(answers)
    print("The answer is {}".format(answers.index(min_ans)))