1
\$\begingroup\$

I've been learning Python and in order to put my skills to the test, I created a simple program that returns the sum of all of the multiples of number num up to 1000.

def get_multiple_sum(num):
    sum = 0
    i = 0
    for i in range(0, 1001):
        if i % num == 0:
            sum += i
        else:
            continue
    return sum

Is this the fastest way to do this? I'm always looking for ways to make my code more efficient.

\$\endgroup\$
4
\$\begingroup\$

range takes an optional third argument, which is the step size for the sequence. For example:

range(0, 10, 3) # Returns [0, 3, 6, 9]

Python also has a built-in sum function that adds up all the numbers in an array, so you could refactor your code to look like this:

def get_multiple_sum(num):
    return sum(range(0, 1000, num))

Performance-wise, this should be much faster, as it doesn't perform 1000 remainder operations and uses a library function which may be optimized by the interpreter.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think for the correct answer, that 1 should be 0. \$\endgroup\$ – Winston Ewert Feb 24 '12 at 1:43
2
\$\begingroup\$
def get_multiple_sum(num):
    sum = 0
    i = 0

This line has no effect. You replace i in the next line

    for i in range(1, 1001):
        if i % num == 0:
            sum += i
        else:
            continue

Continue just before the end of a loop has no effect

    return sum

But as Na7coldwater points out, you can do the whole thing as a quick summation. However, you should be able to figure out a formula for the result of the summation, see Wikipedia which has a list of such formulas: http://en.wikipedia.org/wiki/Summation. Then you can avoid doing a loop at all.

\$\endgroup\$
  • \$\begingroup\$ It is hard to beat an O(1) algorithm. \$\endgroup\$ – Leonid Feb 24 '12 at 4:33
2
\$\begingroup\$

You're trying to sum the multiples of num 1001/num times, which is why I choose n = 1001/num. As others have mentioned, summations can be transformed in \$O(1)\$ operations:

$$ \sum_{i=1}^{1001/\text{num}} i * \text{num} = k \sum_{i=1}^{1001/\text{num}} = \text{num} * \frac{n * (n + 1)}{2} $$

Your code then becomes:

def get_multiple_sum(num):
    n = 1001/num
    return num * n * (n+1)/2
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.