Compute 1000th Prime Number

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 1104 Views - Last Post: 07 May 2013 - 08:35 PM Rate Topic: -----

#1 Sparky1972  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 05-May 13

Compute 1000th Prime Number

Posted 05 May 2013 - 06:12 PM

Hi Guy's.

I am really new to programming and have started with Python following the MIT - I am testing myself as I am considering return to education later in year and convert into Software sector (Development, Testing).
Anyway the assignment I am on is to compute the 1000th prime number. Bear in mind I only have studied up to and including: Print, If, For, While, Tuples.
Here is the code I created for this exercise. I am at the moment checking up to 10 primes until I understand where it is I am going wrong.

count = 1 #count of prime numbers
primes =()#tuple of primes
testnum = 3 #number to be tested for prime
while (count<10):
    for i in range(2,testnum):
        if testnum%i ==0:
            testnum+=1
        else:
            primes = primes + (testnum,)
            testnum+=1
            count+=1
print primes



The result I get is (3, 5, 7, 9, 11, 13, 14, 15, 17). This is obviously incorrect.
I don't think my For loop is correct.

Can anyone point me in the right direction.
Is this normal when starting off to be frustrated and demoralized that I can't get it to work or will I improve?
Thanks.

Is This A Good Question/Topic? 0
  • +

Replies To: Compute 1000th Prime Number

#2 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7950
  • View blog
  • Posts: 13,544
  • Joined: 19-March 11

Re: Compute 1000th Prime Number

Posted 05 May 2013 - 06:29 PM

View PostSparky1972, on 05 May 2013 - 08:12 PM, said:

count = 1 #count of prime numbers
primes =()#tuple of primes
testnum = 3 #number to be tested for prime
while (count<10):
    for i in range(2,testnum):
        if testnum%i ==0:
            testnum+=1
        else:
            primes = primes + (testnum,)
            testnum+=1
            count+=1
print primes



The result I get is (3, 5, 7, 9, 11, 13, 14, 15, 17). This is obviously incorrect.
I don't think my For loop is correct.


It's not. Step through it by hand and you'll see why in half a minute. What happens if testnum %i != 0? Can this ever happen for a non-prime number? I could explain it to you, but it's probably more useful for you to discover it for yourself, so give it a try.


Quote

Is this normal when starting off to be frustrated and demoralized that I can't get it to work or will I improve?


Yes, and yes. Yes it's normal, and yes, you will improve.
Was This Post Helpful? 0
  • +
  • -

#3 Sparky1972  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 05-May 13

Re: Compute 1000th Prime Number

Posted 05 May 2013 - 07:37 PM

Thanks for reply.
My thinking is that if I divide the test number by the number i in the range (2,test number) and the remainder is equal to zero - then the number is not a prime. However - the problem I am seeing with my code is that in the For loop - it doesn't divide the test number by all possible numbers in the range (2, test number).

I am tearing my hair out with it - any other clues??
Was This Post Helpful? 0
  • +
  • -

#4 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7950
  • View blog
  • Posts: 13,544
  • Joined: 19-March 11

Re: Compute 1000th Prime Number

Posted 05 May 2013 - 07:41 PM

It's true that if a number n is divisible by some number i (1<i<n) then the number is not prime. However, that does not imply that if some number n is not divisible by some number i, then that number is prime. Specifically, the fact that 9 is not divisible by 2 does not qualify it as prime.
Was This Post Helpful? 0
  • +
  • -

#5 Sparky1972  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 05-May 13

Re: Compute 1000th Prime Number

Posted 05 May 2013 - 08:00 PM

I know exactly what you are saying - however when I code it, it seems that the For loop doesn't go through and test all the i in the range (2, testnum). I know my coding is messed up.
Can you give me a pointers on the loop.
Was This Post Helpful? 0
  • +
  • -

#6 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7950
  • View blog
  • Posts: 13,544
  • Joined: 19-March 11

Re: Compute 1000th Prime Number

Posted 05 May 2013 - 08:05 PM

So what you want to do is to test each possible divisor (we might refine the range of "possible divisors" later) and only accept the number if it passes all the tests. So when do you want this line to happen?

primes = primes + (testnum,)


What has to have happened before you do this?
Was This Post Helpful? 0
  • +
  • -

#7 Sparky1972  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 05-May 13

Re: Compute 1000th Prime Number

Posted 05 May 2013 - 08:15 PM

View Postjon.kiparsky, on 05 May 2013 - 08:05 PM, said:

So what you want to do is to test each possible divisor (we might refine the range of "possible divisors" later) and only accept the number if it passes all the tests. So when do you want this line to happen?

primes = primes + (testnum,)


What has to have happened before you do this?


Before this the divisor test must pass (testnum%divisor != 0) for the whole range of numbers from 2 to testnum.
Was This Post Helpful? 0
  • +
  • -

#8 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7950
  • View blog
  • Posts: 13,544
  • Joined: 19-March 11

Re: Compute 1000th Prime Number

Posted 05 May 2013 - 08:22 PM

Quote

Before this the divisor test must pass (testnum%divisor != 0) for the whole range of numbers from 2 to testnum.


And that's not what you're doing now...
basically, you want to wrap your isprime test in a method, whose core is a loop that looks like this:

while tests not finished
  if test fails 
    return false   # one failure is enough
  
return true   # if we get here, it's passed all the tests



(pseudocode, obviously)
Was This Post Helpful? 0
  • +
  • -

#9 Sparky1972  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 05-May 13

Re: Compute 1000th Prime Number

Posted 06 May 2013 - 06:40 PM

jon, Thanks for all the help - but I am still struggling but I think getting closer - not sure.
Here is my new code to print 10 primes in a tuple.

count = 1 #count of prime numbers
primes =(2,)#tuple of primes
testnum = 3 #number to be tested for prime
while (count<10):
    for i in range(2,testnum):
        if testnum%i !=0:
            primes = primes + (testnum,)
            testnum+=1
            count+=1
        else:
            testnum+=1
print primes



The problem with the code is for example:
when 5 is the testnum.
It checks 5%2 !=0 which is True. However it proceeds to the next lines and updates the primes, testnum+=1 and count+=1, rather than cheking 5%3 and 5%4.
So for instance when it gets to 9 - it determines that 9 is a prime because 9%2 is True. It never checked 9%3 and so on, which would be false.
This is where I am falling down. I suspect there is something wrong in my for loop.

Am I getting closer - any pointers on the looping error.
Was This Post Helpful? 0
  • +
  • -

#10 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7950
  • View blog
  • Posts: 13,544
  • Joined: 19-March 11

Re: Compute 1000th Prime Number

Posted 06 May 2013 - 08:17 PM

Read my previous post again. Success here is defined as passing all the tests. A number n is prime iff there does not exist some pair of integers p and q such that p * q = n. We know that if n % p = 0, then there exists some integer q such that pq=n, so the existence of one such p is enough to end our search with a negative result. However, we cannot end our search with a positive result until we have exhausted the search space for p. (again, we can refine that search space, once you have the basic loop)

So, to establish that n is prime, we have to have a loop which exhausts the possible candidate integers and finds that none of them is a p, that is, that none of them is involved in a pair p,q such that pq = n.


That is:

while (search space is not exhausted)
  test next candidate
  if result is negative, return failure: n is not prime
end loop
return true. # if we get to this point without returning failure, we have exhausted the search space without proving n is composite, therefore it is prime



Work with this. You're very close to having it right.
Was This Post Helpful? 0
  • +
  • -

#11 Sparky1972  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 05-May 13

Re: Compute 1000th Prime Number

Posted 07 May 2013 - 07:34 PM

Hi jon, I changed my thinking a little in terms of the test so as to eliminate the For loop as I still haven't figured out what I was doing wrong. Finally I think I have a code that works that will print the 1000th prime - how efficient and logical my approach is, this is another discussion. See what you think of it and any suggestions on how to improve.

count = 1 #count of prime numbers
primes =(2,)#tuple of primes
testnum = 3 #number to be tested for prime
B = testnum-1
while (count<1000):
    while (B>=2):
        if testnum%B !=0:
            B = B-1
        else:
            testnum +=1
            B = testnum-1
    primes = primes + (testnum, )
    count +=1
    testnum +=1
    B = testnum - 1
print primes [-1]


Was This Post Helpful? 0
  • +
  • -

#12 Mekire  Icon User is offline

  • D.I.C Head

Reputation: 116
  • View blog
  • Posts: 212
  • Joined: 11-January 13

Re: Compute 1000th Prime Number

Posted 07 May 2013 - 08:02 PM

Seems to work, but you can get faster. There are two simple methods to improve speed. Know that you only have to test a number for divisors up to its square root; and realize that you don't actually need to keep track of what the previous prime numbers were.

-Mek
Was This Post Helpful? 0
  • +
  • -

#13 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7950
  • View blog
  • Posts: 13,544
  • Joined: 19-March 11

Re: Compute 1000th Prime Number

Posted 07 May 2013 - 08:17 PM

View PostMekire, on 07 May 2013 - 10:02 PM, said:

Seems to work, but you can get faster. There are two simple methods to improve speed. Know that you only have to test a number for divisors up to its square root;


You can only use it if you can prove it...
... well, not strictly true, but it's actually worth proving this one. Number theory is a great tool for the programmer, and this is a basic sort of exercise in that area.

Hint: go back to the notion that you're looking for a number p which is part of a pair (p,q)...


Quote

and realize that you don't actually need to keep track of what the previous prime numbers were.


Although keeping track of the previous primes can greatly restrict your search space. If you think about it for a minute, you might see how that works, and how this can speed things up as the numbers get bigger.
The neat thing about working this out for yourself is that you'll have discovered a critical concept in large-scale computation, which is called "dynamic programming". This is a really cool idea, and especially so when you find it for yourself.

This post has been edited by jon.kiparsky: 07 May 2013 - 08:28 PM

Was This Post Helpful? 0
  • +
  • -

#14 Mekire  Icon User is offline

  • D.I.C Head

Reputation: 116
  • View blog
  • Posts: 212
  • Joined: 11-January 13

Re: Compute 1000th Prime Number

Posted 07 May 2013 - 08:24 PM

Quote

Although keeping track of the previous primes can greatly restrict your search space. If you think about it for a minute, you might see how that works, and how this can speed things up as the numbers get bigger.
Yes, but when the numbers get to the size where this is true we are probably going to start using a sieve, rather than brute forcing things. In which case, yes, we will be keeping track of the primes we find (or rather tagging the ones we find aren't prime).

I imagine sieves are a little more than he wants to get into at the moment though.

-Mek
Was This Post Helpful? 0
  • +
  • -

#15 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7950
  • View blog
  • Posts: 13,544
  • Joined: 19-March 11

Re: Compute 1000th Prime Number

Posted 07 May 2013 - 08:25 PM

@Mek - sieves aren't very complicated at all. In fact, they're pretty trivial in python, and worth exploring.

This post has been edited by jon.kiparsky: 07 May 2013 - 08:27 PM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2