# Rookie needs Python Help w/Prime Numbers

Page 1 of 1

## 8 Replies - 4131 Views - Last Post: 08 December 2009 - 11:21 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=141419&amp;s=7ccf1a4913fe135d52c638525e6c7f7c&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 bigdunce

• New D.I.C Head

Reputation: 0
• Posts: 5
• Joined: 23-November 09

# Rookie needs Python Help w/Prime Numbers

Posted 24 November 2009 - 10:14 PM

Hi there!
I'm a returning college student in a Python class and I'm STUCK. I promise I'll post a proper intro later, and forgive me if this topic's been beaten to death, but I'm up to my neck and don't have a lot of time. I've got a HW assignment to 1)write a Python program that determines if a given number is prime and then 2) embed the code as a function to find all primes <= n. I've got a working prime-finder, but I can't figure out how to set it up as a function to check all values <n. First, here's my functional prime-detector:
```def main():
n = input("Enter a number:")
prime = True
for d in range(3,int(n**0.5)+1,2):
if n%d==0:
prime=False
elif n%2==0:
prime = False
if prime==False:
print int(n)," is not prime"
else:
print int(n), "is prime"
main()

```

This is how I have it as a function; it works, but i can't figure out how to attach the range-finder:
```def testfun(n):

prime = True

for d in range(3,int(n**0.5)+1,2):
if n%d==0 or n%2==0:
prime = False
if prime==False:
pass
else:
print int(n),

def main():
n = input("Enter a number:")
testfun(n)
main()
```

and here's a range-finder I wrote that returns "false positives", i.e. odd composites (21, etc.) as prime:
```def findprimes(n):
prime=True
for n in range(2,n+1):
n*=1.0
if n/2==int(n/2)and n!=2:
prime = False
for d in range(2,8):
if n%d==0:
prime=False
if prime==False:
pass
else:
print int(n),

def main():
print "This program finds all primes"
print "up to any value 'n'."
n = input ("enter a number greater than 1:")

findprimes(n)

main()

```

I hope this isn't overload for my first post, and thanks for any light you can shed.

Is This A Good Question/Topic? 0

## Replies To: Rookie needs Python Help w/Prime Numbers

### #2 luke.dunn

• New D.I.C Head

Reputation: 0
• Posts: 1
• Joined: 25-November 09

## Re: Rookie needs Python Help w/Prime Numbers

Posted 25 November 2009 - 06:18 AM

I made this site for people like you:

Prime Numbers in Python

Hope that helps.

Luke

### #3 bigdunce

• New D.I.C Head

Reputation: 0
• Posts: 5
• Joined: 23-November 09

## Re: Rookie needs Python Help w/Prime Numbers

Posted 25 November 2009 - 08:45 AM

I was hoping for some immediate feedback on what I have so far, and maybe some insight into why it isn't working the way I want it to, but I'll have to check that out when I have time.

### #4 bigdunce

• New D.I.C Head

Reputation: 0
• Posts: 5
• Joined: 23-November 09

## Re: Rookie needs Python Help w/Prime Numbers

Posted 25 November 2009 - 09:02 PM

my, don't the crickets sound lovely this time of the evening? So very peaceful and soothing.

### #5 sempron644

• New D.I.C Head

Reputation: 1
• Posts: 19
• Joined: 23-November 09

## Re: Rookie needs Python Help w/Prime Numbers

Posted 26 November 2009 - 02:35 AM

I had to remind myself what a prime number was, but afterall I came up with this function that works!

def prime_finder():
n = input("Enter a number: ")
n = int(n)
if n%2 == 0:
print(" YOUR NUMBER IS NOT A PRIME NUMBER")
elif n%2 == 1:
print(" YOUR NUMBER IS A PRIME NUMBER")

### #6 bigdunce

• New D.I.C Head

Reputation: 0
• Posts: 5
• Joined: 23-November 09

## Re: Rookie needs Python Help w/Prime Numbers

Posted 29 November 2009 - 12:13 AM

Again, not exactly responding to/critiquing what I've already done/posted. I've got a prime-finder; how do I embed it as a function within a main( ) so that it returns all primes < 'n'? Or how do I fix the one that's passing odd composites as prime? Thanks anyway.

### #7 sempron644

• New D.I.C Head

Reputation: 1
• Posts: 19
• Joined: 23-November 09

## Re: Rookie needs Python Help w/Prime Numbers

Posted 29 November 2009 - 12:26 AM

bigdunce, on 28 Nov, 2009 - 11:13 PM, said:

Again, not exactly responding to/critiquing what I've already done/posted. I've got a prime-finder; how do I embed it as a function within a main( ) so that it returns all primes < 'n'? Or how do I fix the one that's passing odd composites as prime? Thanks anyway.

You'll have to use a class and main or the function your using as the first function definition after the __init__ definition.

But I'm not going to disclose my study of the __init__ method this quick, if you did know it then you'd understand how to make it, still...
this type of thing takes some thought!

Yet, theres still a way for you to do what you're doing, hopefully you don't have to turn it in as a student right away...

### #8 baavgai

• Dreaming Coder

Reputation: 7150
• Posts: 14,891
• Joined: 16-October 07

## Re: Rookie needs Python Help w/Prime Numbers

Posted 29 November 2009 - 09:04 AM

```def findprimes(n):
prime=True # I don't understand why this is set here
for n in range(2,n+1): # you just obliterated the n that got passed to you, but ok
n*=1.0 # this seems pointless, maybe detrimental
if n/2==int(n/2)and n!=2:
prime = False
for d in range(2,8): # why check to 8?  what is this supposed to do?
if n%d==0: # this seems nonsensical, you'll only analyze n%7 anyway
prime=False
if prime==False: # ok, still lost
pass
else:
print int(n),

```

Since you take zero advantage of your list of values, you might as well just do it with a simple isPrime kind of function.

This one would work:
```def findprimes(nMax):
def isPrime(n):
if (n==1 or n==2):
return True
if (n%2)==0:
return False
for f in range(3,n/2,2): # start at 3, skip evens, needn't go past half
if (n%f)==0:
return False
return True

primes = []
for n in range(1,nMax+1):
if isPrime(n):
primes.append(n)
return primes

```

However, let's try to do it the right way. There are probably thousands example of this on the web. The thing you want to use for "find primes under n" kind of questions is the "Sieve of Eratosthenes". It's a clever little idea, you can read more here: http://en.wikipedia....of_Eratosthenes

Here's a use of the sieve. The code uses Python's list operations to good effect. If you're unfamiliar with them, you'd do well to read up; they're very handy.

```def findprimes(n):
sieve = [True for i in range(n+1)]
for i in range(3, n+1):
if sieve[i]:
for i in range(i+i, n+1, i):
sieve[i] = False
return [i for i in range(n+1) if sieve[i]]

```

I hope this helps.

### #9 bigdunce

• New D.I.C Head

Reputation: 0
• Posts: 5
• Joined: 23-November 09

## Re: Rookie needs Python Help w/Prime Numbers

Posted 08 December 2009 - 11:21 AM

Sorry I didn't get back here; I was under a deadline and was able to get some help at school. This is what I ended up with:
```def findprimes(n,isprime):

for i in range(2,n+1):
prime = True
for d in range(2,int(i**0.5)+1):
if i%d==0:
prime=False
elif i%2==0:
prime = False
if prime==False:
pass
else:
isprime.append(i)
return (isprime)
def main():
isprime=[]
print "This program finds all primes up to 'n'."
n = input("Enter a number:")
prime = True
findprimes(n,isprime)
print "The primes are:",isprime

main()

```

Not very different from baavgai's idea. I like that sieve too. I tried writing one(as well as a zillion other things!), but it just didn't happen. Thanks for pitching in!