GIDForums  

Go Back   GIDForums > Computer Programming Forums > Python Forum
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read
 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 11-Apr-2006, 22:03
crystalattice's Avatar
crystalattice crystalattice is offline
Aspiring author
 
Join Date: Apr 2004
Location: Japan (again)
Posts: 1,671
crystalattice is just really nicecrystalattice is just really nicecrystalattice is just really nicecrystalattice is just really nicecrystalattice is just really nice

Python script: Prime numbers


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"
__________________
Start Programming with Python-A beginner's guide to programming and the Python language.

Interested in pen & paper role playing games from the "golden age" of gaming? Visit Old School Role-Playing Games
  #2  
Old 15-Apr-2006, 15:16
crystalattice's Avatar
crystalattice crystalattice is offline
Aspiring author
 
Join Date: Apr 2004
Location: Japan (again)
Posts: 1,671
crystalattice is just really nicecrystalattice is just really nicecrystalattice is just really nicecrystalattice is just really nicecrystalattice is just really nice

Re: Python script: Prime numbers


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"
__________________
Start Programming with Python-A beginner's guide to programming and the Python language.

Interested in pen & paper role playing games from the "golden age" of gaming? Visit Old School Role-Playing Games
  #3  
Old 15-Apr-2006, 18:48
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,153
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: Python script: Prime numbers


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
  #4  
Old 16-Apr-2006, 01:47
crystalattice's Avatar
crystalattice crystalattice is offline
Aspiring author
 
Join Date: Apr 2004
Location: Japan (again)
Posts: 1,671
crystalattice is just really nicecrystalattice is just really nicecrystalattice is just really nicecrystalattice is just really nicecrystalattice is just really nice

Re: Python script: Prime numbers


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.
__________________
Start Programming with Python-A beginner's guide to programming and the Python language.

Interested in pen & paper role playing games from the "golden age" of gaming? Visit Old School Role-Playing Games
  #5  
Old 16-Apr-2006, 08:19
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,153
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: Python script: Prime numbers


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
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

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

Network Sites: GIDNetwork · GIDApp · GIDBlog · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 19:48.


vBulletin, Copyright © 2000 - 2014, Jelsoft Enterprises Ltd.