Python code freezes up my computer - Project Euler 58

Question

I am trying to learn python by solving problems from Project Euler. I am stuck on problem 58. The problem states thus:

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49
It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.
If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

Here is the code I wrote for solving this problem. I utilize a primesieve to check for primes, but I didn't know what limit to set the primesieve to. So I let the code tell me when I needed to increase the limit. The code runs fine up to limit=10^8, but when I set it to 10^9, the code freezes up my PC and I have to reboot. Not sure what I'm doing wrong. Please let me know if you need additional information. Thanks!

def primesieve(limit):
    primelist=[]
    for i in xrange(limit):
        primelist.append(i)

    primelist[1]=0
    for i in xrange(2,limit):
        if primelist[i]>0:
            ctr=2
            while (primelist[i]*ctr<limit):
                a=primelist[i]*ctr
                primelist[a]=0
                ctr+=1

    primelist=filter(lambda x: x!=0, primelist)
    return primelist

limit=10**7
plist=primesieve(limit)
pset=set(plist)

diagnumbers=5.0
primenumbers=3.0
sidelength=3
lastnumber=9

while (primenumbers/diagnumbers)>=0.1:
    sidelength+=2
    for i in range(3):
        lastnumber+=(sidelength-1)
        if lastnumber in pset:
            primenumbers+=1
    diagnumbers+=4
    lastnumber+=(sidelength-1)
    if lastnumber>plist[-1]:
        print lastnumber,"Need to increase limit"
        break

print "sidelength",sidelength,"  last number",lastnumber,(primenumbers/diagnumbers)

You might look at http://stackoverflow.com/q/2068372/344286 for some tips on improving your sieve — Wayne Werner, Jan 21 '16 at 18:30
The point of project Euler is brute force won't solve the problem and you need to do some maths to reduce the amount of calculation/memory needed. — Peter Wood, Jan 21 '16 at 19:05

score 0 · Accepted Answer · answered Jan 21 '16 at 18:36

0

Even though you are using xrange, you are still generating a list of of size 10**9 when making your primesieve. That use a large amount of memory, and is likely your problem.

Instead, you might consider writing a function that checks if a number, N, is prime or not, by checking of any number between (2,N**.5) divide the number evenly. Then, you can go about generating the corner numbers and just perform primality testing.

answered Jan 21 '16 at 18:36

Garrett R

2,687
11
15

Thank you, Garrett. I always assumed the primesieve was the most efficient way of detecting primality, but it may not be true in all cases. The trial division method worked in a jiffy. – Naren Jan 21 '16 at 19:28

score 0 · Answer 2 · answered Jan 21 '16 at 19:03

Here are some things that you can do to make your prime generator more efficient:

def primesieve(limit):
    primelist=[]

    # Don't create a list of all your numbers up front.
    # And even if you do, at least skip the even numbers!
    #for i in xrange(limit):
    #    primelist.append(i)

    # Skip counting - no even number > 3 is prime!
    for i in xrange(3, limit, 2):

        # You only need to check up to the square root of a number:
        # I *thought* that there was some rule that stated that a number
        # was prime if it was not divisible by all primes less than it,
        # but I couldn't find that for certain. That would make this go
        # a lot faster if you only had to check primes and numbers greater
        # than the greatest prime found so far up to the square root of
        # the number
        for divisor in xrange(3, int(i**0.5)+1, 2):
            if not i % divisor:  # no remainder, so sad
                break
        else:
            # loop exited naturally, number has no divisors hooray!
            primelist.append(i)

    # Need to put the number 2 back, though
    primelist.insert(0, 2) 
    return primelist

This uses the mess out of my CPU (100% or more, hooray!) but hardly uses any memory (like, a couple MB RAM by 7 minutes in). My CPU is only 2.something GHz, and this took over 7 minutes so far for 10**8 as the maximum prime.

If you look at the post I linked in the comment there are some much better approaches for generating primes, but these are some simple improvements.

Thank you, Wayne. I solved the problem by checking for primality using trial division, but what you've suggested makes a lot of sense. Don't know why I didn't think of this earlier! I'll keep it mind for my future programming endeavors. — Naren, Jan 21 '16 at 19:30

Python code freezes up my computer - Project Euler 58

2 Answers2