Need helping writing Prime number code

Thread Solved

Join Date: Nov 2009
Posts: 4
Reputation: ChaseRLewis is an unknown quantity at this point 
Solved Threads: 0
ChaseRLewis ChaseRLewis is offline Offline
Newbie Poster

Need helping writing Prime number code

 
0
  #1
24 Days Ago
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; 24 Days Ago at 9:48 pm.
Reply With Quote Quick reply to this message  
Join Date: Nov 2009
Posts: 4
Reputation: ChaseRLewis is an unknown quantity at this point 
Solved Threads: 0
ChaseRLewis ChaseRLewis is offline Offline
Newbie Poster
 
0
  #2
24 Days Ago
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
  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.
Reply With Quote Quick reply to this message  
Join Date: Oct 2004
Posts: 4,002
Reputation: vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice 
Solved Threads: 927
Moderator
vegaseat's Avatar
vegaseat vegaseat is online now Online
DaniWeb's Hypocrite
 
0
  #3
23 Days Ago
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 ...
  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; 23 Days Ago at 5:51 pm. Reason: spelling
May 'the Google' be with you!
Reply With Quote Quick reply to this message  
Join Date: Dec 2006
Posts: 1,008
Reputation: woooee is a jewel in the rough woooee is a jewel in the rough woooee is a jewel in the rough 
Solved Threads: 285
woooee woooee is offline Offline
Veteran Poster
 
0
  #4
23 Days Ago
Wouldn't this lead to an infinite loop.
  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; 23 Days Ago at 7:56 pm.
Linux counter #99383
Reply With Quote Quick reply to this message  
Join Date: Nov 2009
Posts: 4
Reputation: ChaseRLewis is an unknown quantity at this point 
Solved Threads: 0
ChaseRLewis ChaseRLewis is offline Offline
Newbie Poster
 
0
  #5
23 Days Ago
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.
Reply With Quote Quick reply to this message  
Join Date: Nov 2009
Posts: 4
Reputation: ChaseRLewis is an unknown quantity at this point 
Solved Threads: 0
ChaseRLewis ChaseRLewis is offline Offline
Newbie Poster
 
0
  #6
23 Days Ago
Originally Posted by woooee View Post
Wouldn't this lead to an infinite loop.
  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.
Reply With Quote Quick reply to this message  
Join Date: Oct 2004
Posts: 4,002
Reputation: vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice 
Solved Threads: 927
Moderator
vegaseat's Avatar
vegaseat vegaseat is online now Online
DaniWeb's Hypocrite
 
0
  #7
23 Days Ago
Originally Posted by ChaseRLewis View Post
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 ...
  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 ...
  1. print( [0]*5 ) # [0, 0, 0, 0, 0]
Last edited by vegaseat; 23 Days Ago at 10:41 am.
May 'the Google' be with you!
Reply With Quote Quick reply to this message  
Join Date: Oct 2004
Posts: 4,002
Reputation: vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice 
Solved Threads: 927
Moderator
vegaseat's Avatar
vegaseat vegaseat is online now Online
DaniWeb's Hypocrite
 
0
  #8
20 Days Ago
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 ...
  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!
May 'the Google' be with you!
Reply With Quote Quick reply to this message  
Join Date: Dec 2006
Posts: 1,008
Reputation: woooee is a jewel in the rough woooee is a jewel in the rough woooee is a jewel in the rough 
Solved Threads: 285
woooee woooee is offline Offline
Veteran Poster
 
1
  #9
20 Days Ago
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.
Linux counter #99383
Reply With Quote Quick reply to this message  
Join Date: Oct 2004
Posts: 4,002
Reputation: vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice 
Solved Threads: 927
Moderator
vegaseat's Avatar
vegaseat vegaseat is online now Online
DaniWeb's Hypocrite
 
0
  #10
20 Days Ago
Originally Posted by woooee View Post
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.
May 'the Google' be with you!
Reply With Quote Quick reply to this message  
Reply

Tags
number, prime, recursion

This thread has been marked solved.
Perhaps start a new thread instead?
Message:


Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC