| | |
Need helping writing Prime number code
Thread Solved |
•
•
Join Date: Nov 2009
Posts: 4
Reputation:
Solved Threads: 0
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.
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.
•
•
Join Date: Nov 2009
Posts: 4
Reputation:
Solved Threads: 0
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 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.
New code is
Python Syntax (Toggle Plain Text)
def Prime(x,y): n=2 if x == 1: Prime(x+1,y) elif x == 2: print (2) Prime(x+1,y) elif x <= 0: print ("Number must be a positive integer") else: while n < n+1: if n > int(x/n): print(x) x=x+1 n=2 elif x > y: print("end") break elif x%n==0: x=x+1 n=2 else: n=n+1
Recursion just isn't meant for this process now completely iterative it works much better.
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 ...
For n = 10000000 it takes about 4 seconds. Once you get close to one billion your memory resources start complaining.
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)
def fast_primes(n): """ uses an Eratosthenes sieve to return a list of prime numbers from 2 to < n """ siv = range(n+1) siv[1] = 0 sqn = int(n**0.5) for i in range(2, sqn+1): if siv[i] != 0: siv[2*i:n//i*i+1:i] = [0]*(n//i-1) return filter(None, siv)
Last edited by vegaseat; 23 Days Ago at 5:51 pm. Reason: spelling
May 'the Google' be with you!
•
•
Join Date: Dec 2006
Posts: 1,008
Reputation:
Solved Threads: 285
0
#4 23 Days Ago
Wouldn't this lead to an infinite loop.
Python Syntax (Toggle Plain Text)
def Prime(x,y): n=2 if x == 1: Prime(x+1,y) elif x == 2: print (2) Prime(x+1,y) elif x <= 0: print ("Number must be a positive integer" else: while n < n+1: ## <=====
Last edited by woooee; 23 Days Ago at 7:56 pm.
Linux counter #99383
•
•
Join Date: Nov 2009
Posts: 4
Reputation:
Solved Threads: 0
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.
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.
•
•
Join Date: Nov 2009
Posts: 4
Reputation:
Solved Threads: 0
0
#6 23 Days Ago
•
•
•
•
Wouldn't this lead to an infinite loop.Python Syntax (Toggle Plain Text)
def Prime(x,y): n=2 if x == 1: Prime(x+1,y) elif x == 2: print (2) Prime(x+1,y) elif x <= 0: print ("Number must be a positive integer" else: while n < n+1: ## <=====
Convoluted, but at the time decided it wasn't worth sitting down and figuring out why my conditional statement was messed up, lol.
0
#7 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.
Here is an example ...
Python Syntax (Toggle Plain Text)
# exploring Python's slicing operator # can be used with any indexed sequence like strings, lists, ... # syntax --> seq[begin : end : step] # step is optional # defaults are index begin=0, index end=len(seq)-1, step=1 # -begin or -end --> count from the end backwards # step = -1 reverses sequence # if you feel lost, put in the defaults in your mind # use a list as a test sequence a = [0, 1, 2, 3, 4, 5, 6, 7, 8] print( a[3:6] ) # [3,4,5] # if either index is omitted, beginning or end of sequence is assumed print( a[:3] ) # [0,1,2] print( a[5:] ) # [5,6,7,8] # negative index is taken from the end of the sequence print( a[2:-2] ) # [2,3,4,5,6] print( a[-4:] ) # [5,6,7,8] # extract every second element print( a[::2] ) # [0, 2, 4, 6, 8] # step=-1 will reverse the sequence print( a[::-1] ) # [8, 7, 6, 5, 4, 3, 2, 1, 0] # no indices just makes a copy (which is sometimes useful) b = a[:] print( b ) # [0, 1, 2, 3, 4, 5, 6, 7, 8] # slice in a few elements starting at index 3 b[3:] = [9, 9, 9, 9] + b[3:] print( a ) # [0, 1, 2, 3, 4, 5, 6, 7, 8] print( b ) # [0, 1, 2, 9, 9, 9, 9, 3, 4, 5, 6, 7, 8]
Python Syntax (Toggle Plain Text)
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!
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 ...
Can someone check this out for accuracy? I would appreciate it!
python Syntax (Toggle Plain Text)
# prevents the list of primes from getting too large # and taxing the computer's memory # tested with Python2 and Python3 by vegaseat def primes_range(low=2, high=100): """ returns a list of primes in range low to high """ if low == 2: prime_list = [2] else: prime_list = [] # make sure start is an odd number start = low if start % 2 == 0: start += 1 # range() needs to do odd numbers only ... for n in range(start, high+1, 2): prime = True for divisor in range(3, int(n**0.5)+1, 2): if n % divisor == 0: prime = False break if prime and n >= low: prime_list.append(n) return prime_list low = 1000000 high = low + 100 print( primes_range(low, high) ) """result for primes_range(1000000, 1000100) --> [1000003, 1000033, 1000037, 1000039, 1000081, 1000099] """ print('-'*60) low = 1000000000 high = low + 100 print( primes_range(low, high) ) """result for primes_range(1000000000, 1000000100) --> [1000000007, 1000000009, 1000000021, 1000000033, 1000000087, 1000000093, 1000000097] """ print('-'*60) low = 1000000000000 high = low + 100 print( primes_range(low, high) ) """result for primes_range(1000000000000, 1000000000100) --> Python 2.5.4 [1000000000039L, 1000000000061L, 1000000000063L, 1000000000091L] Python 3.1.1 [1000000000039, 1000000000061, 1000000000063, 1000000000091] """
May 'the Google' be with you!
•
•
Join Date: Dec 2006
Posts: 1,008
Reputation:
Solved Threads: 285
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.
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
0
#10 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.
May 'the Google' be with you!
![]() |
Similar Threads
- Prime number program (C++)
- Weird Prime Number Checker (C++)
- Code Snippet: Prime number generator with remarkable speed (C++)
- Help with Prime number code. (C++)
- Prime Number Generator slow (C++)
- Urgent: Plz Help me,Prime Number Program Problem (C++)
- Code for checking prime number or not (C++)
- Code Snippet: Prime Number Generator (Python) (Python)
- Average of prime number between 1 & 100 (C#)
Other Threads in the Python Forum
- Previous Thread: Parse Logic/Code Need
- Next Thread: I require help with making 3 simple program/functions
| Thread Tools | Search this Thread |
account arithmetic array basic beginner binary c++ class college conversion count digit display dynamic echo factorial function game guess guessing integer java line linked list math maximum method ms number numbers numbertoword output php prime primenumbersinrange program programing python query read record recursion recursive regex result return scrolledtext sequential sets sql string tree trim vbnet visual word







