4 Replies - 2678 Views - Last Post: 05 October 2010 - 07:29 AM Rate Topic: -----

#1 GeekSpot101  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 02-September 10

1000th Prime

Posted 11 September 2010 - 12:19 AM

Good morning! I've been up all night trying to make this work and I finally got it to come up with the right answer. I'm very new to Python and want to know if anyone has tips to make this more clean? Also, while I was debugging this (man did that make me want to pull my hair out), I had an issue that seemed to resolve itself where n was initialized as 5 and when I tried the operation (n//2) it told me I could not divide a str by an int. I don't have the code anymore as I wrote over it so not sure if anyone will know what I'm talking about. Thanks for any help.


n=5               #So I don't get an error in line 7
count=3                 #Starting at 5 which has 3 primes before it
while count <= 1000:    #1000th prime
    i=2                 #Start division at 2
    while i <= n//2+1:  #Keep going until I is one more than half number being tested for primality
        x=n%i           #make x be remainder of division of 2 through one half number +1
        if x==0:        #If it is 0 then it is not prime, so stop and try next number   
            break       
        else:
            if i == n//2+1:  #If i increases to the point where it is half value + 1 of testing number 
                count+=1     #then it is prime add one to the prime count.
        i+=1                 #Regardless add one to i for next test. 
    n+=1                     #Try next number.
print(n-1)
    

    


Is This A Good Question/Topic? 0
  • +

Replies To: 1000th Prime

#2 Nallo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 161
  • View blog
  • Posts: 247
  • Joined: 19-July 09

Re: 1000th Prime

Posted 11 September 2010 - 06:08 AM

Your program is fine. As for readability there are 3 changes I would make:
candidate = 5
count = 3
while count <= 1000:
    for divisor in range(2, candidate // 2 + 1):
        remainder = candidate % divisor
        if remainder == 0:
            break
    #this else only gets executed when we didnt run into a break
    #so we can get rid of the if i == n // 2 + 1
    else:
        count += 1
    candidate += 1
print(candidate - 1)


1. Use meaningful variable names instead of the short x,n,i.
2. Instead of the inner while loop I would use a for loop. Looking at your program you need to read the lines 4,5 and search for line 12 in the while block before you understand what you loop over. With a for loop that information is in one line (easier to read)
3. I used Pythons for break else. Probably best explained with an example:
test = 11 #try this with 5 instead of 11 (to see that the else block below will not be executed)
for i in range(10):
    if i == test:
        break
else:
    print("We didnt run into a break in the corresponding loop block")
print("finished")



As for the "could not divide a str by an int" error ... I dont see how that could happen. Maybe you had something like the following in your program:
n = input("give me a number") #python 3.x
#input in python 3.x returns a string, so the following fails
print(n//2)


in which case you first have to typecast the string to an int:
n = input("give me a number") #python 3.x
n = int(n)
print(n//2)


Was This Post Helpful? 1
  • +
  • -

#3 GeekSpot101  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 02-September 10

Re: 1000th Prime

Posted 11 September 2010 - 03:03 PM

View PostNallo, on 11 September 2010 - 05:08 AM, said:

As for the "could not divide a str by an int" error ... I dont see how that could happen. Maybe you had something like the following in your program:
n = input("give me a number") #python 3.x
#input in python 3.x returns a string, so the following fails
print(n//2)


in which case you first have to typecast the string to an int:
n = input("give me a number") #python 3.x
n = int(n)
print(n//2)


Thank you! That is exactly what happened, I thought it was weird that I would have to use n=int(n) but that is how I worked around it before I gave up and decided to just put 1000 right in the code, rather than ask n=input("Which prime do you want?"). Is there a way to specify in the input what type you want it to be like... number = input.int("Give me a number")? Thanks again, I like your use of the for rather than my while, I'll have to keep it in mind for next time that I don't always have to use while :)
Was This Post Helpful? 0
  • +
  • -

#4 Nallo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 161
  • View blog
  • Posts: 247
  • Joined: 19-July 09

Re: 1000th Prime

Posted 11 September 2010 - 05:12 PM

>Is there a way to specify in the input what type you want it to be like...

Nope, input will always return a string (in python 3.x).
If you want to make sure user input is an integer number you could do the following:
while True: #input loop
    userinput = input("gimme an integer")
    try:
        n = int(userinput)
    except:
        print("bad input. try again")
        continue
    break
print("input was %i"%n)


This post has been edited by Nallo: 11 September 2010 - 05:15 PM

Was This Post Helpful? 0
  • +
  • -

#5 Brewer  Icon User is offline

  • Awesome
  • member icon

Reputation: 178
  • View blog
  • Posts: 1,044
  • Joined: 14-June 10

Re: 1000th Prime

Posted 05 October 2010 - 07:29 AM

Personally, when I am messing with prime numbers I use a function I call isPrime(). Then I use a for loop or a range to check for primes between 2 given numbers.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1