[Tutor] Writing a prime number program using upper bound of square root of n

[Steven D'Aprano]

On Mon, 23 Aug 2010 04:55:15 am Nick wrote:

> Is there a way I can set my email program to insert the ">" symbol to
> mark what I'm replying to without manually doing it?

Depends on your mail client.

What are you using? Outlook?


> I get the picture now, that was a great example.  I wrote some code
> last night before going to bed that did what you were saying checking
> if it was divisible by 2, 3, 5, or 7.  I'm going to paste that. And
> so in my range function in this code could the upper bound be n*.5
> instead of n+1 ?


I think you mean n**0.5, not half n.


> primes = [2, 3, 5, 7]
> def p(n):
>     for i in range(3, n+1, 2):
>         if i % 3 == 0 or i % 5 == 0 or i % 7 == 0:
>             pass
>         else:
>             primes.append(i)


Some criticisms... 

(1) The name "p" for the function doesn't give much hint as to what it 
does. What does it mean? 

"print"?
"probability"?
"prime numbers less than n"?
"the first n primes"?
"is n a prime number"?
"prime factorization of n"?

You know the answer *now*, but will you remember in six months?


(2) Using global data is usually a bad thing. You should be able to call 
the function twice without breaking things, but in this case, if you 
call it twice, the primes list will have numbers added twice.


My suggestion is to move the list of primes into the function, rather 
than a global variable, and start with a function like this:


def primes(n):
    """Return a list of primes less than or equal to n."""
    if n < 2:
        return []  # No primes less than two, so we're done.
    results = [2]
    for i in xrange(3, n+1):
        if is_prime(i):
            results.append(i)
    return results


Now all you need is to write a function is_prime(n) that decides whether 
or not n is prime.


def is_prime(n):
    """Returns True if n is prime, otherwise False."""
    if n == 2:
        return True
    elif (n % 2 == 0) or (n < 2):
        return False
    # If we get here, we know that n is an odd number.


is_prime() is not complete. You have to write the rest.


(Note: this approach isn't the most efficient way of doing it, but it is 
probably the simplest. Once you have this working, you can think about 
ways to make it more efficient.)


-- 
Steven D'Aprano