Python script: Prime numbers

crystalattice · #1 11-Apr-2006, 22:03

Here's another script I wrote. This one lists the prime numbers from 2 to 1000. Again, feel free to use this as needed; just save it with .py as the extension.

Python Code:

###############################################################
#List prime numbers from 2 to 1000.
#Author:  Cody Jackson
#Date:  4/10/06
###############################################################

import math #sqrt function

def prime(num):
    """Determine if a given number is prime"""
    
##The highest value that needs to be compared is the square root of the number
    for x in range (2, math.sqrt(num)): 
        if num%x == 0:  #if remainder is 0, the number is not prime
            return 1
            break
                
#---Generate range of numbers
for val in range(2, 1001):
    is_prime = prime(val)
    if is_prime != 1:   #if returned value is 1, the number isn't prime
        print val, " is prime.\n"

crystalattice · #2 15-Apr-2006, 15:16

Okay, so I found out I screwed up somewhere. The code above will let a few non-prime values slip by, which I didn't catch. It will also give you an error message because the range() function is looking for integers. However, the math.sqrt() function will give you floating-point numbers. You can fix the error by changing it to int(math.sqrt(num)).

I worked on the program most of the morning but I can't figure out why I can't get the range() part of it to work with the sqrt function, so here's the revised version using brute force. It's not elegant but it works, though I don't recommend it for large numbers. If someone can figure out what I did wrong, I'd appreciate it.

Python Code:

import math #sqrt function

def prime(num):
    """Determine if a given number is prime"""
    
    for x in range (2, num):    #ensure sqrt is an integer
        if num%x == 0:  #if remainder is 0, the number is not prime
            return 1
            break
                       
#---Generate range of numbers
for val in range(2, 1001):
    is_prime = prime(val)
    if is_prime != 1:   #if returned value is 1, the number isn't prime
        print val, " is prime.\n"

davekw7x · #3 15-Apr-2006, 18:48

Quote:

Originally Posted by crystalattice

It will also give you an error message because the range() function is looking for integers. However, the math.sqrt() function will give you floating-point numbers. You can fix the error by changing it to int(math.sqrt(num)).

I got a warning message, not an error, which I cleaned up by using the int() thing.

Quote:

Originally Posted by crystalattice

I can't get the range() part of it to work

Did you try:

Python Code:

    for x in range (2, int(math.sqrt(num)+1)):

Work out a few examples:

For example when num = 4, sqrt(num) = 2 (exactly) and the loop in the original script doesn't execute at all (so it doesn't catch the fact that 2 divides 4) (for x in range (2, 2) never gets into the loop since the index is not less than the upper limit here)

When num = 6, sqrt(num) = 2.449... Since converting to an int truncates, the loop won't execute for x = 2. (so it doesn't catch the fact that 2 divides 6)

Work it out (by hand) for 8, 9, 15, 25, 35... or until you get really, really tired of it, and come to a logical conclusion:

Since it won't go through the loop for an index that is not less than the upper limit, what we really need for the upper limit is a number that is the next larger integer greater than sqrt(num) to make sure the loop doesn't quit too soon. Truncating the sqrt and incrementing by one (or incrementing by one then truncating) works for me.

Thanks for the learning opportunity for a new field for me. I like your tutorials and I appreciate your efforts.

Regards,

Dave

crystalattice · #4 16-Apr-2006, 01:47

You're right, it is a warning and not an error. My bad.

I did notice that it didn't like it when the sqrt = 2. I tested a few things and realized that it wouldn't make a list if the range was (2,2), but I didn't think about adding 1 to the max value. Actually I did, but I didn't think it would be "correct" since you're changing the max value. However, I now realize that you're not changing the original number, just the number that's used in the loop.

Thanks for correcting me on this. I messed with it for about an hour or two today and couldn't get my mind around it. I realize now that I've been away from programming for too long; the last time I wrote a program was for my C++ class a year and a half ago.

But that's why I got a new Python text book and I'm working through the problems. I'll have more "code snippets" as I read through the book. Glad you like the material.

davekw7x · #5 16-Apr-2006, 08:19

Quote:

Originally Posted by crystalattice

I'll have more "code snippets"

I am looking forward to seeing and learning more. I almost feel as if I am "cheating" by letting you go through the text(s) and showing some simple applications for me to build on. Maybe some day I'll read a book on it.

Regards,

Dave

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Python script: Celsius to Fahrenheit	crystalattice	Python Forum	0	11-Apr-2006 22:00
subscript error in coding	warborules	C Programming Language	6	27-Nov-2005 17:16
Linear Search	eccoflame	C Programming Language	3	19-Apr-2005 08:36
prime numbers	quasimof	C++ Forum	1	01-Nov-2004 19:35
Help w/ prime # determination	crystalattice	C Programming Language	17	18-Apr-2004 21:43

Python script: Prime numbers

Re: Python script: Prime numbers

Re: Python script: Prime numbers

Re: Python script: Prime numbers

Re: Python script: Prime numbers