944,141 Members | Top Members by Rank

Ad:
  • Python Discussion Thread
  • Marked Solved
  • Views: 3173
  • Python RSS
Nov 2nd, 2009
0

Need helping writing Prime number code

Expand Post »
Newbie Here

Edit: This is not homework, I am a chemical engineering student and a math minor. I'm doing programming on the side to help me automate certain calculations later in my career. Also always had a healthy interest in programming. I just read the not doing homework for people sticky at the top and want to throw out there i'm not a computer programming student.

I'm creating a program to create list of prime numbers code. It has taught me a good amount about recursions statements and how while statements can be used to maximize performance for given recursion limits.

My problem is I can only search a range of ~ 1000 numbers before the recursion limit is reached. I know there is some basic improvements I can do but my current concerns:

1. The program recurs the program Prime(x) with program Prime(x+1) to check the next x value across the interval [x,x+970]. Finding all prime numbers over that interval. However, I can't find out how to define the upper bound x+970 since recurring Prime(x+1) increases the upper bound.
So how can I create a fixed upper bound with only one variable being inputted, x.

2. Is their a way to have the program run for the interval clear the stack, than run the next interval [x+971,x+970+971] if an interval greater than the recursion limit was desired? Till a single number is too large for the platform I would expect there to be a way around the recursion limit.

This is one of my first independent programs and I just couldn't find good answers to these questions.
def Prime(x):
  n=2
  if x > 972: #My upper limit is 972 and my lower limit is x,  
      print "end"        #how do I make the upper limit a function of x
  elif x == 1:                # when I have to recur Prime(x+1)?
    Prime(x+1)
  elif x == 2:
    print (2)
    Prime(x+1) 
  elif x <= 0:
    print ("Number must be a positive integer")
  else:
    while n < n+1:
      if n > int(x/n):
        print(x)
        break
      elif x%n==0:
        break
      else:
        n=n+1
    Prime(x+1)
Last edited by ChaseRLewis; Nov 2nd, 2009 at 9:48 pm.
Similar Threads
Reputation Points: 7
Solved Threads: 2
Junior Poster in Training
ChaseRLewis is offline Offline
67 posts
since Nov 2009
Nov 2nd, 2009
0
Re: Need helping writing Prime number code
K found an easy anwser to my interval issue. Just remove the concept of recursion completely. Cool, only been programming for a day : P read half this free book and got something to show for it.

New code is
Python Syntax (Toggle Plain Text)
  1. def Prime(x,y):
  2. n=2
  3. if x == 1:
  4. Prime(x+1,y)
  5. elif x == 2:
  6. print (2)
  7. Prime(x+1,y)
  8. elif x <= 0:
  9. print ("Number must be a positive integer")
  10. else:
  11. while n < n+1:
  12. if n > int(x/n):
  13. print(x)
  14. x=x+1
  15. n=2
  16. elif x > y:
  17. print("end")
  18. break
  19. elif x%n==0:
  20. x=x+1
  21. n=2
  22. else:
  23. n=n+1
I just made a second input variable to define the upper bound, but having a fixed one would be nice in some circumstances.

Recursion just isn't meant for this process now completely iterative it works much better.
Reputation Points: 7
Solved Threads: 2
Junior Poster in Training
ChaseRLewis is offline Offline
67 posts
since Nov 2009
Nov 3rd, 2009
0
Re: Need helping writing Prime number code
For programs like this, recursion is not a very good idea. Calling a function, even itself, is one of the slower things in programming because of the stack control. You will find that in the faster prime algorithms repeated function calls are absent.

Here is an example of one of the fastest algorithms. Notice that it only has three function calls, range() is called twice and filter() is called once ...
python Syntax (Toggle Plain Text)
  1. def fast_primes(n):
  2. """
  3. uses an Eratosthenes sieve to return a list of
  4. prime numbers from 2 to < n
  5. """
  6. siv = range(n+1)
  7. siv[1] = 0
  8. sqn = int(n**0.5)
  9. for i in range(2, sqn+1):
  10. if siv[i] != 0:
  11. siv[2*i:n//i*i+1:i] = [0]*(n//i-1)
  12. return filter(None, siv)
For n = 10000000 it takes about 4 seconds. Once you get close to one billion your memory resources start complaining.
Last edited by vegaseat; Nov 3rd, 2009 at 5:51 pm. Reason: spelling
Moderator
Reputation Points: 1333
Solved Threads: 1404
DaniWeb's Hypocrite
vegaseat is offline Offline
5,792 posts
since Oct 2004
Nov 3rd, 2009
0
Re: Need helping writing Prime number code
Wouldn't this lead to an infinite loop.
Python Syntax (Toggle Plain Text)
  1. def Prime(x,y):
  2. n=2
  3. if x == 1:
  4. Prime(x+1,y)
  5. elif x == 2:
  6. print (2)
  7. Prime(x+1,y)
  8. elif x <= 0:
  9. print ("Number must be a positive integer"
  10. else:
  11. while n < n+1: ## <=====
Last edited by woooee; Nov 3rd, 2009 at 7:56 pm.
Reputation Points: 741
Solved Threads: 694
Nearly a Posting Maven
woooee is online now Online
2,312 posts
since Dec 2006
Nov 3rd, 2009
0
Re: Need helping writing Prime number code
I understand most of that code from a mathematics point, but siv[2*i:n//i*i+1:i] = [0]*(n//i-1) doesn't make some sense to me if someone can help. what do the colon's mean in the first part? Also the [0] in the second part obviously doesn't mean multiply by zero, so what does that mean?

I'm mainly learning from free guides and haven't quite finished the book, but these notations I haven't seen before.

Pretty cool, so function calls are a major influence on program speed makes sense.
Reputation Points: 7
Solved Threads: 2
Junior Poster in Training
ChaseRLewis is offline Offline
67 posts
since Nov 2009
Nov 3rd, 2009
0
Re: Need helping writing Prime number code
Click to Expand / Collapse  Quote originally posted by woooee ...
Wouldn't this lead to an infinite loop.
Python Syntax (Toggle Plain Text)
  1. def Prime(x,y):
  2. n=2
  3. if x == 1:
  4. Prime(x+1,y)
  5. elif x == 2:
  6. print (2)
  7. Prime(x+1,y)
  8. elif x <= 0:
  9. print ("Number must be a positive integer"
  10. else:
  11. while n < n+1: ## <=====
No the point of the program is to continue until it finds the all the primes. I couldn't find out why another restriction I put in was terminating early so I made it an infinite loop where it would end when x > y which was the elif statement. So if x never became greater than y it would be infinite, but since x increases every loop eventually it would be so the loop would terminate.

Convoluted, but at the time decided it wasn't worth sitting down and figuring out why my conditional statement was messed up, lol.
Reputation Points: 7
Solved Threads: 2
Junior Poster in Training
ChaseRLewis is offline Offline
67 posts
since Nov 2009
Nov 4th, 2009
0
Re: Need helping writing Prime number code
I understand most of that code from a mathematics point, but siv[2*i:n//i*i+1:i] = [0]*(n//i-1) doesn't make some sense to me if someone can help. what do the colon's mean in the first part? Also the [0] in the second part obviously doesn't mean multiply by zero, so what does that mean?

I'm mainly learning from free guides and haven't quite finished the book, but these notations I haven't seen before.

Pretty cool, so function calls are a major influence on program speed makes sense.
This operation is called slicing and it avoids function calls. Slicing can be done with any sequence.

Here is an example ...
Python Syntax (Toggle Plain Text)
  1. # exploring Python's slicing operator
  2. # can be used with any indexed sequence like strings, lists, ...
  3. # syntax --> seq[begin : end : step]
  4. # step is optional
  5. # defaults are index begin=0, index end=len(seq)-1, step=1
  6. # -begin or -end --> count from the end backwards
  7. # step = -1 reverses sequence
  8. # if you feel lost, put in the defaults in your mind
  9.  
  10. # use a list as a test sequence
  11. a = [0, 1, 2, 3, 4, 5, 6, 7, 8]
  12.  
  13. print( a[3:6] ) # [3,4,5]
  14. # if either index is omitted, beginning or end of sequence is assumed
  15. print( a[:3] ) # [0,1,2]
  16. print( a[5:] ) # [5,6,7,8]
  17.  
  18. # negative index is taken from the end of the sequence
  19. print( a[2:-2] ) # [2,3,4,5,6]
  20. print( a[-4:] ) # [5,6,7,8]
  21.  
  22. # extract every second element
  23. print( a[::2] ) # [0, 2, 4, 6, 8]
  24.  
  25. # step=-1 will reverse the sequence
  26. print( a[::-1] ) # [8, 7, 6, 5, 4, 3, 2, 1, 0]
  27.  
  28. # no indices just makes a copy (which is sometimes useful)
  29. b = a[:]
  30. print( b ) # [0, 1, 2, 3, 4, 5, 6, 7, 8]
  31.  
  32. # slice in a few elements starting at index 3
  33. b[3:] = [9, 9, 9, 9] + b[3:]
  34. print( a ) # [0, 1, 2, 3, 4, 5, 6, 7, 8]
  35. print( b ) # [0, 1, 2, 9, 9, 9, 9, 3, 4, 5, 6, 7, 8]
The second part [0]*(n//i-1) multplies a list of zeroes ...
Python Syntax (Toggle Plain Text)
  1. print( [0]*5 ) # [0, 0, 0, 0, 0]
Last edited by vegaseat; Nov 4th, 2009 at 10:41 am.
Moderator
Reputation Points: 1333
Solved Threads: 1404
DaniWeb's Hypocrite
vegaseat is offline Offline
5,792 posts
since Oct 2004
Nov 6th, 2009
0
Re: Need helping writing Prime number code
To get very large prime numbers without causing memory problems, you indeed have to apply a range to keep the list relative short, like this example shows ...
python Syntax (Toggle Plain Text)
  1. # prevents the list of primes from getting too large
  2. # and taxing the computer's memory
  3. # tested with Python2 and Python3 by vegaseat
  4.  
  5. def primes_range(low=2, high=100):
  6. """
  7. returns a list of primes in range low to high
  8. """
  9. if low == 2:
  10. prime_list = [2]
  11. else:
  12. prime_list = []
  13. # make sure start is an odd number
  14. start = low
  15. if start % 2 == 0:
  16. start += 1
  17. # range() needs to do odd numbers only ...
  18. for n in range(start, high+1, 2):
  19. prime = True
  20. for divisor in range(3, int(n**0.5)+1, 2):
  21. if n % divisor == 0:
  22. prime = False
  23. break
  24. if prime and n >= low:
  25. prime_list.append(n)
  26. return prime_list
  27.  
  28. low = 1000000
  29. high = low + 100
  30. print( primes_range(low, high) )
  31.  
  32. """result for primes_range(1000000, 1000100) -->
  33. [1000003, 1000033, 1000037, 1000039, 1000081, 1000099]
  34. """
  35.  
  36. print('-'*60)
  37.  
  38. low = 1000000000
  39. high = low + 100
  40. print( primes_range(low, high) )
  41.  
  42. """result for primes_range(1000000000, 1000000100) -->
  43. [1000000007, 1000000009, 1000000021, 1000000033, 1000000087,
  44. 1000000093, 1000000097]
  45. """
  46.  
  47. print('-'*60)
  48.  
  49. low = 1000000000000
  50. high = low + 100
  51. print( primes_range(low, high) )
  52.  
  53. """result for primes_range(1000000000000, 1000000000100) -->
  54. Python 2.5.4
  55. [1000000000039L, 1000000000061L, 1000000000063L, 1000000000091L]
  56. Python 3.1.1
  57. [1000000000039, 1000000000061, 1000000000063, 1000000000091]
  58. """
Can someone check this out for accuracy? I would appreciate it!
Moderator
Reputation Points: 1333
Solved Threads: 1404
DaniWeb's Hypocrite
vegaseat is offline Offline
5,792 posts
since Oct 2004
Nov 6th, 2009
1
Re: Need helping writing Prime number code
There are several online pages to do that.
http://primes.utm.edu/curios/includes/primetest.php
is one found on this very good page
http://primes.utm.edu/

Your program works correctly, at least for the range you tested.
Reputation Points: 741
Solved Threads: 694
Nearly a Posting Maven
woooee is online now Online
2,312 posts
since Dec 2006
Nov 7th, 2009
0
Re: Need helping writing Prime number code
Click to Expand / Collapse  Quote originally posted by woooee ...
There are several online pages to do that.
http://primes.utm.edu/curios/includes/primetest.php
is one found on this very good page
http://primes.utm.edu/

Your program works correctly, at least for the range you tested.
Thanks for the info and the works. I haven't had time to check the limits of that program. Since Python handles extremely large integers, I imagine computer memory will be the limit again.
Moderator
Reputation Points: 1333
Solved Threads: 1404
DaniWeb's Hypocrite
vegaseat is offline Offline
5,792 posts
since Oct 2004

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in Python Forum Timeline: Parse Logic/Code Need
Next Thread in Python Forum Timeline: I require help with making 3 simple program/functions





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC