Project Euler Problem 12 - C++

Project Euler Problem 12 - C++

You currently check for divisors up to dividend/2. You can reduce this to sqrt(dividend), which is asymptotically faster. A special case may be needed if dividend is square.

My C++ code for problem 12 (which does essentially the same as yours, but uses this lower limit, and also just counts divisors rather than storing them in the set) takes about 1 second

Euler Project problem #12 Python code gives weird results

The problem is you are using facs as a global variable and you are only appending to the item. You should make it a member of allfacof() so that it clears out after each value.
If you look into facs then you will find it equals

1, 1, 3, 1, 2, 3, 6, 1, 2, 5, 10 ...

Optimise the solution to Project Euler 12 (Python)

My answer here isn't pretty or elegant, it is still brute force. But, it simplifies the problem space a little and terminates successfully in less than 10 seconds.

Getting factors of n:
Like @usethedeathstar mentioned, it is possible to test for factors only up to n/2. However, we can do better by testing only up to the square root of n:

let n = 36
=> factors(n) : (1x36, 2x18, 3x12, 4x9, 6x6, 9x4, 12x3, 18x2, 36x1)

As you can see, it loops around after 6 (the square root of 36). We also don't need to explicitly return the factors, just find out how many there are... so just count them off with a generator inside of sum():

import math

def get_factors(n):
    return sum(2 for i in range(1, round(math.sqrt(n)+1)) if not n % i)

Testing the triangular numbers

I have used a generator function to yield the triangular numbers:

def generate_triangles(limit):
    l = 1
    while l <= limit:
        yield sum(range(l + 1))
        l += 1

And finally, start testing:

def test_triangles():
    triangles = generate_triangles(100000)
    for i in triangles:
        if get_factors(i) > 499:
            return i

Running this with the profiler, it completes in less than 10 seconds:

$ python3 -m cProfile euler12.py 

361986 function calls in 8.006 seconds

The BIGGEST time saving here is get_factors(n) testing only up to the square root of n - this makes it heeeaps quicker and you save heaps of memory overhead by not generating a list of factors.

As I said, it still isn't pretty - I am sure there are more elegant solutions. But, it fits the bill of being faster :)

Need help optimizing solution for Project Euler problem #12

Use the underlying mathematical structure, this will dramatically change your program's running time. This also applies to problem 10, by the way; if you can't do it in a few milliseconds, you've used a massively inefficient algorithm. In fact, I advise you to work on problem 10 first, because problem 12 builds on it.

I'm going to give a better algorithm for problem 12 below, but first, here's an observation that should speed up your program significantly. If two numbers x and y are coprime (i.e. they have no common divisor other than 1), then d(x·y) = d(x)·d(y). In particular, for a triangle number, d(n·(n+1)) = d(n)·d(n+1). So instead of iterating over the triangle numbers n·(n+1), iterate over n: this will significantly reduce the size of the arguments passed to d(n).

If you do that optimization, you'll notice that you compute d(n) twice in a row (once as d((n-1)+1) and once as d(n)). This suggests that caching the result of d is a good idea. The algorithm below does it, but also computes d bottom-up rather than top-down, which is more efficient because multiplying is a lot faster than factoring.

---

Problem 10 can be solved by a simple application of the sieve of Eratosthenes. Fill up an array of booleans (i.e., a bit vector) of size 2000000 such that with sieve[i]==true if i is prime; then sum up the numbers for which sieve[i]==true.

Problem 12 can be solved by a generalization of the sieve of Eratosthenes. Instead of making sieve[i] a boolean indicating whether i is prime, make it a number indicating the number of ways in which it is non-prime, i.e. the number of divisors of i. It is easy to modify the basic sieve of Eratosthenes to do that: rather than set sieve[x*y] to false, add 1 to it.

Several subsequent project Euler problems benefit from a similar approach.

One issue you may have is that in problem 12, it's not clear when to stop computing the sieve. You can go two ways about it:

1. compute the sieve by chunks on demand, a worthwhile programming exercise in itself (this will require more complex code that the second method)

2. or start by overestimating a bound: find some triangle number that has over 500 divisors, you know you'll stop before or at that number.

You can gain more time if you realize that you only need to care about odd numbers, since d(2^k·n) = (k+1)·d(n) if n is odd, and finding k and n given only (2^k·n) is fast on a binary computer. I'll leave the details of that optimization as an exercise.

Project euler 12 python code doesn't run, is it slow or what?

The while x!=1 is putting you in an infinite loop when the number is a prime number. That's because only the number itself can divide it, and your range does not get that number.

For example, when x is 3, 5, or 7 (all primes) -

In [12]: list(range(3,3,2))
Out[12]: []

In [14]: list(range(3,5,2))
Out[14]: [3]

In [15]: list(range(3,7,2))
Out[15]: [3, 5]

The only way to break out of the while x!=1 loop is when x==1, but that does not happen because x never gets divided by itself. You can avoid that by letting your range go further.

---

Related Topics