Calculating prime numbers

Question

I am now doing the MIT opencourse thing, and already the second assignment, I feel it has left me out in the cold. http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/assignments/pset1a.pdf

The specifics of it, are to write something that can calculate the 1000th prime number. We only know about the print, ==, =, 1=,if, else, elif, while, %, -,+,*,/, commands I think. We also don't yet know about importing libraries.

My Idea of how it would work is to take an odd number and try to divide it by, 3,4,5,6,7,8,9 and if %n !=0, then add a number to NumberofPrimes variable starting with 11 as the base of the tests, and assigning it a base value of 4 at the base of NumberofPrimes, though I don't know if that is even right, because I wouldn't know how to display the 1000th prime number.

Am I close?

The latest incarnation of it is as follows:

##calculate the 1000th prime number
potprime = 3
numberofprime = 1
cycle = if potprime%3 = 0:
            break
        if potpimre%4 = 0:
            break
        if potprime%5 = 0:
            break
        if potprime%6 = 0:
            break
        if potprime%7 = 0:
            break
        if potprime%8 = 0:
            break
        if potprime%9 = 0:
            break
        numberofprime + 1
        potprime + 1

if potprime%2 == 0:
    potprime = potprime + 1
if potprime != 0:
    cycle

Where exactly am I going wrong? Walk me through it step by step. I really want to learn it, though I feel like I am just being left out in the cold here.

At this point, it would be more beneficial for me to see how a proper one could be done rather than doing this. I have been working for 3 hours and have gotten nowhere with it. If anybody has a solution, I would be more than happy to look at it and try to learn from that.

Answer 1

Looks like I am late

It is quite straight forward that if a number is not divisible by any prime number, then that number is itself a prime number. You can use this fact to minimize number of divisions.

For that you need to maintain a list of prime numbers. And for each number only try to divide with prime numbers already in the list. To optimize further it you can discard all prime numbers more than square root of the number to be tested. You will need to import sqrt() function for that.

For example, if you test on 1001, try to test with 3, 5, 7, 11, 13, 17, 19, 23, 29 and 31. That should be enough. Also never try to find out if an even number is prime. So basically if you test an odd number n, then after that test next number: (n + 2)

Have tested the below code. The 1000th prime number is 7919. Not a big number!!

Code may be like:

from math import sqrt

primeList = [2]
num = 3
isPrime = 1

while len(primeList) < 1000:
    sqrtNum = sqrt(num)

    # test by dividing with only prime numbers
    for primeNumber in primeList:

        # skip testing with prime numbers greater than square root of number
        if num % primeNumber == 0:
            isPrime = 0
            break
        if primeNumber > sqrtNum:
            break

    if isPrime == 1:
        primeList.append(num)
    else:
        isPrime = 1

    #skip even numbers
    num += 2

# print 1000th prime number
print primeList[999]

Answer 2

The following code is gross, but since 1000 is indeed a small index, it solves your problem in a fraction of a second (and it uses only the primitives you are supposed to know so far):

primesFound = 0
number = 1

while primesFound < 1000:
    number = number + 1          # start from 2

    # test for primality
    divisor = 2
    numberIsPrime = True
    while divisor*divisor <= number:   # while divisor <= sqrt(number)
        if number % divisor == 0:
            numberIsPrime = False
            break
        divisor = divisor + 1

    # found one?
    if numberIsPrime:
        primesFound = primesFound + 1

print number

You can test the solution here. Now you should find a more efficient solution, optimize and maybe go for the 1000000-th prime...