1

I have already solved problem 5 of Project Euler (What is the smallest positive number that is evenly divisible (with no remainder) by all of the numbers from 1 to 20?), but I want to find a faster way (currently 0.000109195709229 seconds).

I tried a dynamic approach, but when I run the code below (it is just the first part) I don't understand why d[var][counter] gets +1 if I explicitly wrote d[i][counter] += 1.

n = 20
d = {1:[0,1] + [0]*19}  #a dictionary that assigns to each number a list of its prime factorization
for i in xrange(2,3):   #I changed n+1 with 3 for simplicity
    var = i
    counter = 2
    notDone = True
    while notDone:
        if var % counter == 0:
            var /= counter
            print var, d[var]
            d[i] = d[var]           #i has the same prime factorization of var ...
            print var, d[var]
            d[i][counter] += 1      #... except for 1 number (counter)
            print var, d[var]        #wtf?
            notDone = False
        else:
            counter += 2 if counter != 2 else 1

This is the outcome:

1 [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
1 [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
1 [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

why does this happen?

Pigna
  • 2,792
  • 5
  • 29
  • 51

1 Answers1

1

At the line

d[i] = d[var]

the variable d[i] will hold the same list object as d[var], as lists are mutable.

Instead you need a copy of d[var], that you can get e.g. by

d[i] = d[var][:]
Berci
  • 544
  • 1
  • 7
  • 10