# Python Code Improvements?

Hi,

This is my solution to ECOO(2005) - Fractorials.

Is there any place where I can improve my code? Any advice would be appreciated. Thanks!

``````prime_list = [2]
fractorial = {}

def prime_factor(n):
prime_factorization = {}
for j in range(len(prime_list)):
while n % prime_list[j] == 0:
n = n // prime_list[j]
update_dict(prime_factorization, prime_list[j])
if len(prime_factorization) == 0:
update_dict(prime_factorization, n)
prime_list.append(n)

return prime_factorization

def update_dict(dict, n):
if n in dict:
dict[n] += 1
else:
dict[n] = 1

def main():
number = int(input())
if number == 1:
print("Fractorial(1) = 1")
else:
for i in range(2, number + 1):
prime_factorization = prime_factor(i)
for key in prime_factorization:
if key in fractorial:
if prime_factorization[key] > fractorial[key]:
fractorial[key] = prime_factorization[key]
else:
fractorial[key] = prime_factorization[key]

fractorial_value = 1
for key in fractorial:
fractorial_value *= key ** fractorial[key]
print(f"Fractorial({number}) = {fractorial_value}")

main()
``````

This much nesting is difficult to track, it contains a large number of possible paths making it all kinds of difficult to deal with and error prone.

You are creating an iterable and iterating through it to iterate through your iterable.

I gave up on trying to follow along in what happens in that code, it is all very intertwined, and the behaviour of prime_factor may change.
Iâ€™d like to see things being carried out one at a time if at all possible
Without digging too much into it myself, I imagine you would do something like creating a function to factorize a number (doesnâ€™t need to be efficient because your numbers are 22 or less I believe)
Then apply it to each of your numbers
Then figure out which of those you are keeping
Then multiply them together
â€¦emphasis on then, theyâ€™re separate steps, in sequence, not being done simultaneously which is what you currently do (which is why you â€śneedâ€ť global variables to track your state, causing your factorization function to change its behaviour between calls, this is not a good thing). I may very well have gotten the algorithm wrong.

I would also be tempted to go with a much more naive solution considering that the largest number is only around 200 million, and the results could be hard-coded into the program since there are only 22 of them

The way you keep down complexity (and you have to, because it doesnâ€™t take much more than this to start running into human limits) is by splitting things up into small tasks which are easy to understand by themselves. Then you increasingly combine those together in higher-level tasks which are also understandable because the other parts donâ€™t need to be understood at the same time

Iâ€™d want the main function to look something like this:

``````get input, convert
stuff = create list of 1-x
stuff = get factors(stuff)
stuff = decide what to keep(stuff)
stuff = multiply together(stuff)
write stuff to screen
``````
1 Like

Wow. Thanks for your advice. Iâ€™m on it. So basically, you want it to be modular so that it is easy to understand and check for errors. Just one question, what do you mean by

â€¦emphasis on then , theyâ€™re separate steps, in sequence, not being done simultaneously which is what you currently do (which is why you â€śneedâ€ť global variables to track your state, causing your factorization function to change its behaviour between calls, this is not a good thing). I may very well have gotten the algorithm wrong.

What do you mean by behaviour between calls? Sorry for the dumb question, Iâ€™m new to programming.

You have a global variable which affects how it behaves. It also changes that variable, itâ€™s really difficult to figure out what it does, and I imagine if you called it with other arguments in a different order it wouldnâ€™t behave right at all.

Modular is such a big difficult word. Iâ€™m just looking for doing one thing at a time. Right now you have control jumping all over the place. Lots of nesting is a pretty good indication that something should be written differently, though the interaction with that function which changes its own behaviour makes it all a lot worse.

If you look at my mock-up of what i want your main function to look like, those are completely separate steps that donâ€™t interact with each other and happen in sequence

Also, for clarification, this was basically my algorithm.

Say i want fractorial(6).

Then I will loop through the numbers from 2 to 6 (I donâ€™t consider 1).
So I prime factor each number and update the fractorial dictionary, which is initially empty. Soâ€¦

Prime factor 2 -> 2 ^ 1
Fractorial dict becomes {2:1}

Prime factor 3 -> 3 ^ 1
Fractorial Dict becomes {2:1, 3:1}

Prime factor 4 -> 2 ^ 2
Since 2 is an existing key in fractorial dictionary and the power (2) is greater than the current power of 2 in fractorial dictionary(1). Fractorial Dict becomes {2:2, 3, 1}.

Prime factor 5 -> 5 ^ 1
Fractorial Dict becomes {2^2, 3:1, 5:1}

Prime factor 6 -> 2 ^ 1 x 3 ^ 1
Since 2 and 3 are existing keys in fractorial, but their powers (1 and 1) are less than or equal to the existing powers in fractorial dictionary for 2 and 3 (2 and 1). Then I will not update fractorial dictionary.

Therfore fractorial dictionary is {2:2, 3:1, 5:1} and I multiply all that to get the final value.

Thatâ€™s the same algorithm Iâ€™m describing, I believe.

Oh and apparently Counter (like defaultdict, this is also a version of a dict) has a sweet operation where it can keep the max count of each item when merging Counters:

``````from collections import Counter

a = Counter([2, 3, 3, 3, 5])
b = Counter([2, 2, 3, 7, 7, 7])
print(a)
print(b)
c = a | b  # <-- union
print(c)
``````

output:

``````Counter({3: 3, 2: 1, 5: 1})
Counter({7: 3, 2: 2, 3: 1})
Counter({3: 3, 7: 3, 2: 2, 5: 1})
``````

But. Even though itâ€™s super neat it has the cost of figuring out what exactly it does, and most readers probably wouldnâ€™t know what it does either. I learned about it now

Gets worse yet when wanting to apply that operation on an arbitrary amount of such Counters. You could put it in a loop. The really neat way though is with reduce:

``````from functools import reduce
from collections import Counter
from operator import or_

counters = [a, b, c, d]  # let's pretend those exist
maxcounts = reduce(or_, counters)
``````

Super neat. Neat here mostly meaning thereâ€™s a lot to understandâ€¦ So donâ€™t bother. Yet.

Howâ€™s this?

``````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 < 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] > 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] < fractorial[key]:
#      break
#
# fractorial[key] = prime_factorization[key]
#
# since it has less code.

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

return value

main()
``````

Not done looking, but surely, rather than passing in an empty dict, create one inside that function instead, and return it?

â€¦Oh youâ€™re doing it multiple times.
Iâ€™d rather you returned multiple results, and consolidate them later
So your factorisation function would return a list of factors.
And then you would have several such lists, which you then, in a separate step figure out what to keep

Itâ€™s doing two things at once. And Iâ€™m not a fan, because itâ€™s easy to separate that

â€¦oh they are two steps. but. theyâ€™re likeâ€¦ taking turns. I want ALL the factors before doing anything else

Anyway. Itâ€™s better. And itâ€™s starting to be more of an opinion than an obvious problem

This is what I came up with:

``````from collections import Counter
from functools import reduce
from operator import or_, mul

def main():
x = int(input())
xs = range(1, x+1)
factors = [Counter(prime_factors(x)) for x in xs]
consolidated = reduce(or_, factors)
multiplied = reduce(mul, consolidated.elements())
print(multiplied)

def prime_factors(n):
if n == 1:
return [1]
divisor = 2
result = []
while divisor <= n:
if n % divisor == 0:
result.append(divisor)
n //= divisor
else:
divisor += 1
return result

if __name__ == '__main__':
main()
``````

I suppose that it illustrates that past getting the factors, itâ€™s all just massaging the data into the format you want. Think assembly lines. You put your data on one assembly line. Then that feeds into the next. At the end you have the result.
What you donâ€™t do is switch assembly lines back and forth.

Thatâ€™s where I want a defaultdict, if youâ€™re going to do it that way. You can make it default to 0.

``````from collections import defaultdict
fractorial = defaultdict(int)
print(fractorial[3])  # 0 (default)
``````

Oh and I like this. `//` instead of `/` is the correct way to do it. Otherwise youâ€™re using floats for no reason at all.

I noticed you imported various modules that I have not come across anywhere in the the text I read â€śIntroduction to Python Programmingâ€ť by Daniel Liang. Could you list some useful and commonly used modules that one should know.