ECOO contest 2015: Problem 1 This is my solution to the ECOO 2015 contest, problem 1, Fractorials. I'd appreciate any advice to improve readability, style, organization, etc.



def main():
    number = int(input())
    fractorial = {}
    for i in range(2, number + 1):
        prime_factorization = prime_factor(i)
        update_fractorial(prime_factorization, fractorial)

    print(compute_fractorial_value(fractorial))


def prime_factor(number):
    primes = [2, 3, 5, 7, 11, 13, 17, 19]
    dict = {}
    i = 0
    while i &lt; len(primes):
        p = 0
        while number % primes[i] == 0:
            number = number // primes[i]
            p += 1

        if p != 0:
            dict[primes[i]] = p

        i += 1

    return dict


def update_fractorial(prime_factorization, fractorial):
    for key in prime_factorization:
        if key in fractorial:
            if prime_factorization[key] &gt; fractorial[key]:
                fractorial[key] = prime_factorization[key]
        else:
            fractorial[key] = prime_factorization[key]

        # Or should I replace the if/else statements with:
        #
        # if key in fractorial:
        #   if prime_factorization[key] &lt; fractorial[key]:
        #      break
        #
        # fractorial[key] = prime_factorization[key]
        #
        # since it is shorter.


def compute_fractorial_value(fractorial):
    value = 1
    for key in fractorial:
        value *= key ** fractorial[key]

    return value


main()
Overall the code is quite easy to read, but it is more complicated than it needs to be.




    fractorial = {}
    for i in range(2, number + 1):
        prime_factorization = prime_factor(i)
        update_fractorial(prime_factorization, fractorial)

    print(compute_fractorial_value(fractorial))



I would expect the name fractorial to be either the final integer or the function which computes it. Perhaps fractorial_factorization would be a clearer name.

compute_fractorial_value doesn't actually do anything specific to fractorials. Perhaps compose_factorization or multiply_powers?

The algorithm used to compute the prime factorisation of the fractorial is correct, but overkill. If \$p\$ is a prime and \$a\$ is a positive integer, under what condition is \$p^a\$ a factor of the \$n\$th fractorial?




def prime_factor(number):
    primes = [2, 3, 5, 7, 11, 13, 17, 19]
    dict = {}
    i = 0
    while i &lt; len(primes):
        p = 0
        while number % primes[i] == 0:
            number = number // primes[i]
            p += 1

        if p != 0:
            dict[primes[i]] = p

        i += 1

    return dict



Apart from the hard-coded primes, this is a standard implementation. I would suggest that p is more conventionally used to denote primes[i], so perhaps power would be a less surprising name.




def update_fractorial(prime_factorization, fractorial):
    for key in prime_factorization:
        if key in fractorial:
            if prime_factorization[key] &gt; fractorial[key]:
                fractorial[key] = prime_factorization[key]
        else:
            fractorial[key] = prime_factorization[key]

        # Or should I replace the if/else statements with:
        #
        # if key in fractorial:
        #   if prime_factorization[key] &lt; fractorial[key]:
        #      break
        #
        # fractorial[key] = prime_factorization[key]
        #
        # since it is shorter.



Shorter still, and more explicit:

def update_fractorial(prime_factorization, fractorial):
    for key in prime_factorization:
        if key not in fractorial or prime_factorization[key] &gt; fractorial[key]:
            fractorial[key] = prime_factorization[key]


Although it's preferable to avoid repeating the lookup. The efficient way of doing this is

def update_fractorial(prime_factorization, fractorial):
    for key, val in prime_factorization.items():
        if key not in fractorial or val &gt; fractorial[key]:
            fractorial[key] = val





def compute_fractorial_value(fractorial):
    value = 1
    for key in fractorial:
        value *= key ** fractorial[key]

    return value



Apart from the previous comment about the name, the only thing I'd say here is that if you really want to scale this up, multiplying lots of small numbers is best done on a tree-like basis. I.e. you pair up the numbers, multiply each pair, pair up again, multiply again, ... But that's overkill for this problem.




main()



This is half-way between the naïve approach of not defining main() at all and just dumping its contents at the end, and the "best practice" approach of

if __name__ == "__main__":
    main()


Might as well get used to the best practice approach now.