Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
June 20th, 2012, 01:38 PM
 jsdecker
Registered User

Join Date: Jun 2012
Posts: 3
Time spent in forums: 1 h 42 m 20 sec
Reputation 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
June 20th, 2012, 08:43 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,140
Time spent in forums: 1 Month 3 Weeks 2 Days 7 h 17 m 40 sec
Reputation Power: 455
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```
__________________
[code]Code tags[/code] are essential for python code!

Last edited by b49P23TIvg : June 20th, 2012 at 09:31 PM.

#3
June 20th, 2012, 09:11 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,140
Time spent in forums: 1 Month 3 Weeks 2 Days 7 h 17 m 40 sec
Reputation Power: 455
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.

#4
June 20th, 2012, 09:26 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,140
Time spent in forums: 1 Month 3 Weeks 2 Days 7 h 17 m 40 sec
Reputation Power: 455

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

You have written this nightmare
Code:
```for ITEM in LIST:
LIST.remove(ITEM)```

#5
June 20th, 2012, 09:28 PM
 jsdecker
Registered User

Join Date: Jun 2012
Posts: 3
Time spent in forums: 1 h 42 m 20 sec
Reputation 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!

#6
June 20th, 2012, 09:51 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,140
Time spent in forums: 1 Month 3 Weeks 2 Days 7 h 17 m 40 sec
Reputation Power: 455
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.

#7
June 20th, 2012, 10:01 PM
 jsdecker
Registered User

Join Date: Jun 2012
Posts: 3
Time spent in forums: 1 h 42 m 20 sec
Reputation 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.

 Viewing: Dev Shed Forums > Programming Languages > Python Programming > New to programming, need help optimizing a simple prime generator