[Tutor] RE: Prime Numbers

[Ike Hall]

Hi Ahimsa,

I should have told you at the beginning, that I wrote aprogram to do exactly
this (find primes between x and y) afew years ago.  It actually is not that
complex, but merely involves thinking in math for a few minutes.  (for me,
this is easy, but for others, I realize this is not always the case...hence,
I will try to replicate what I did, from memory, since that snippet of code
lives on a computer far away, with comments to try to explain what is going
on.)

First, I decided that what I would do is define a function,
prime(x,y) that returned a tuple containing all primes between x and y.
code below:

#So, we are going to need the math module, because I
#wanted to speed it up using sqrt()...
#and the types module, because I want to make sure
#that x and y are integers, or floats, or longs.

import math
from types import *

def prime(x,y):
  #first, I want to be sure that I have numbers for x and y

  if type(x) != IntType or FloatType or LongType:
    print 'I need numbers people!'
    return  None
  elif type(y)!= IntType or FloatType or LongType:
    print 'I need numbers people!'
    return None
  else:
    pass

  #next, we want to find out which is smaller, and make #sure that is 'x'
  if x>y:
    dummy = x
     x=y
     y=dummy

  #now we also want to make sure that there is at least one
  #integer between x and y (floats cannot be primes, but
  # primes can lie between 2 floats if there is an integer
  #between them

  if int(y) < int(x)+1:
     print 'There are no integers between '+str(x)'+ and '+str(y)+',
therefore, no primes'
     return None

  #now we have done all the checks we need, so we now turn our numbers into
integers if they are not already
  #we add one to int(x) or long(x) to get the next integer, since we want
primes between x and y
  if type(x)==FloatType:
     try:
          x=int(x)+1
     except(OverflowError):
          x=long(x)+1

  if type(y)==FloatType:
     try:
           y=int(y)
     except(OverflowError):
           y=long(y)

  #now for the meat of the program:

  #to save us some time, we can just check every odd number between x and y
  # since we know that 2 is the only even prime number
  #also, we will not check any negative numbers, since they cannot be
prime...even if their positive
  #counterpart is (since -x =(x*-1) or (-x*1), assuming x is prime)
  primes=[]
  if 1 in range(x,y):primes.append(1)
  if 2 in range(x,y):primes.append(2)

  if y<=3:
    if y==3:primes.append(3)
    return primes
  if x<3:start=3
  elif x%2: start=x
  else:start=x+1
  for i in range(start,y,2):
    high=int(math.sqrt(i))   #we only check between 2 and sqrt(i)
    primeflag=1
    for j in range(2, high):
       if not i%j:
             primeflag=0
       else:
             pass
    if primeflag:
        primes.append(i)

  return tuple(primes)


I hope this helps...Im not sure if I put a bug in there, as I havent tested
this, but I did test the loop part, and I am sure that it works.  as you can
see, its not that complicated....but for larger and larger numbers, it could
take some time....
BTW, if you want to go from 1 to anything instead of x to anything, you only
need to check each number against the prime numbers that are lower than its
square root...and since you add them to the list in order, you just loop
over the list that already exists....anyway, I hope this helps some...and if
not, I hope it doesnt make you throw your hands in the air screaming....

Ike
----- Original Message -----
From: "ahimsa" <ahimsa@onetel.net.uk>
To: <tutor@python.org>
Sent: Tuesday, February 25, 2003 1:06 PM
Subject: [Tutor] RE: Prime Numbers


> Brett, Ike, Gerrit, Timothy (sorry, if I have left anyone out):
>
> Thank you all for replying to my query - in truth, I have to confess it
was
> far more info than I needed, but was useful in a number of ways:
>
> 1. It helped me realise that the algorithm that I was trying to draft some
> working code to figure out primes was *hopelessly* inadequate to the task
> required
> 2. It helped me realise that actually a simple sounding problem (find the
> prime numbers between 1 and 28, for e.g. ) is actually a seemingly very
> complex problem
> 3. I don't feel too bad about not being able to work it out myself given
the
> fairly sophisticated (from my perspective) code that you folk fed back to
me
> 4. There is - as always - still so much to learn, and that I will revisit
this
> problem when I have a clearer understanding of what is required and how to
> think through the terms of the problem.
> 5. And, thank you for the code snippets: I file these away for later
review
> and I am happy to be able to report that I am obviously learning more than
I
> realise since the code no longer looks entirely like a strange Martian
> dialect.
>
> Once again - thanks, and so, till next time ... all the best
>
> Andrew
>
> _______________________________________________
> Tutor maillist  -  Tutor@python.org
> http://mail.python.org/mailman/listinfo/tutor
>