Need helping writing Prime number code

[ChaseRLewis]

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
 [B] if x > 972:[/B] #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)

[ChaseRLewis]

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

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

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.

[vegaseat]

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 ...

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)

For n = 10000000 it takes about 4 seconds. Once you get close to one billion your memory resources start complaining.

[woooee]

Wouldn't this lead to an infinite loop.

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:     ## <=====

[ChaseRLewis]

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.

[ChaseRLewis]

Wouldn't this lead to an infinite loop.

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:     ## <=====

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.

[vegaseat]

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 ...

# 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]

The second part [0]*(n//i-1) multplies a list of zeroes ...

print( [0]*5 )  # [0, 0, 0, 0, 0]

[vegaseat]

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 ...

# 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]
"""

Can someone check this out for accuracy? I would appreciate it!

[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.

[vegaseat]

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.