#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2012
    Posts
    3
    Rep Power
    0

    New to programming, need help optimizing a simple prime generator


    Hey everyone, the title pretty much says it all, but I'm trying to teach myself to program and decided to start with Python. As kind of fun tests for myself I've been working Project Euler problems, and this one deals with finding the sum of all primes below 2 million. I wrote this program, which is accurate and seems to be fast enough for limits of up to 50000 or so. However, it becomes impossibly slow when I try to move up to 6 or 7 figure limits. I've been wracking my brain about this for a few days but I can't figure out how to make it faster.

    I know that adding primes to a growing list instead of removing composites from the list would probably be better, but can't figure out how to do it. Any tips or explanations on that or another approach? Thanks in advance!

    Code:
    import math
    lim = 10000
    primes = range(2, lim)
    n = 0
    p = 0
    while p < math.sqrt(lim):
        p = primes[n]
        for x in primes:
            if x % p == 0 and x != p:
                primes.remove(x)
        n = n + 1
    print sum(primes)
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,996
    Rep Power
    481
    Well, you sound like a nice guy so I'll ... dang it. I can't just give it to you. Look up the sieve of Erothosthenes (Greek name I cannot spell without research, sorry.)
    In executable Iverson notation (www.jsoftware.com) a solution is
    Code:
    $ jconsole
       a=: +/p:i.p:^:_1[2000000
    Last edited by b49P23TIvg; June 20th, 2012 at 09:31 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,996
    Rep Power
    481
    I'll give you a couple solutions anyway. This will probably ruin my life, and destroy your discovery drama as you need to improve your prime number generator to solve more of the project Euler problems. Teach programming first. So don't read this post. Thanks. And if you do read this post, run doctest as I've shown and learn to use it in your own programs. And learn about the array module, or about scipy.
    Code:
    import array
    
    '''
        # make an efficient
        #  (small)
        #  (small because each entry consumes a byte instead of
        #   space for an entire object)
        # array for each number.  Put a 1 in each entry that is composite.
    '''
    
    def sieve(n):
        '''
            doctest--->use:  $ python -m doctest -v thisfile.py
            >>> sieve(8)
            array('b', [1, 1, 0, 0, 1, 0, 1, 0, 1])
        '''
        composites = array.array('b',(0 for i in range(n+1)))
        composites[0] = composites[1] = 1
        for (i,composite,) in enumerate(composites):
            if not composite:
                for j in range(i**2,n+1,i):
                    composites[j] = 1
        return composites
    
    c = sieve(1999999) # array composites are marked with a 1 to 2e6
    
    print('there is a 1 for the composite indexes')
    print('and a 0 for the prime indexes.')
    print('0 through 20 inclusive:')
    print(c[:21])
    
    p=[j for (j,i)in enumerate(c) if not i]  # primes to 2e6
    print('Project Euler #10:' + str(sum(p)))
    This runs in under 5 seconds on my several year old laptop computer. A question: why in this loop is it sufficient to start from the square of the prime number?
    Code:
                for j in range(i**2,n+1,i):
    The fastest python prime generator I've found is to install the primes program from the ubuntu bsdgames package, or from where ever you find it, and run this program as a separate process using the subprocess module.
    Last edited by b49P23TIvg; June 20th, 2012 at 09:37 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,996
    Rep Power
    481

    As for your code


    Don't modify an object you're iterating over.

    You have written this nightmare
    Code:
    for ITEM in LIST:
        LIST.remove(ITEM)
    [code]Code tags[/code] are essential for python code and Makefiles!
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2012
    Posts
    3
    Rep Power
    0
    Well, I think you've convinced me that what I really need to do here is to forget about these specific problems for a while and go back to the basics a bit: get more experience programming and learning just to think computationally, and add more tools to my python arsenal (for example, I have no idea what arrays even are...). I might've been getting ahead of myself--attempting conversation before I know all the key vocabulary, so to speak. Thanks!
  10. #6
  11. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,996
    Rep Power
    481
    golly gosh I didn't intend to smack you that hard.

    You did, after all, know to use the square root of the maximum number as an upper limit for your division test.

    And, by solving the project Euler problems you can read solutions posted by others in many languages including python.

    Also, if you actually do learn to use doctest (or whatever testing methods) you'll be way ahead of most people. Tests give you confidence that your code works. Tests show how to use your code.
    [code]Code tags[/code] are essential for python code and Makefiles!
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2012
    Posts
    3
    Rep Power
    0
    Haha, I wouldn't call it a smack. You didn't crush my hopes and dreams or anything. I just feel like I legitimately need to get a better grasp of the basics. I'm going to go back to some online tutorials I've been learning through, for now.

IMN logo majestic logo threadwatch logo seochat tools logo