Need help with an assignment from the MIT opencourse. Calculating prime numbers.

Question

So, I have a very shotty background in programing and I have, for a very long time, attempted to learn through various lessons, though, no matter how good the lesson or tutorial is said to be, it always loses me at some point. For example the CarlH lectures lost me at around unit 5 part 1 and 2 where it jumped the shark and neglected to say how to run, compile, execute code. I got confused and decided to try something else. I tried Invent your own computer games with python though it lost me at around the hangman chapter. I have also tried other things, though there is always that point where it goes "Here, it is easy! Try this...!" and of course it is something that in no way I understand. 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 If anybody could help me. I don't even know where to begin. Thanks. Hopefully this won't be another ones where it jumps the shark.

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

Your math is failing you. A prime number is a number that has 2 divisors: 1 and itself. You are not testing the numbers for primality.

Answer 2

For one thing, I'm pretty sure that in Python, if you want to have an if statement that tests whether or not A = B, you need to use the == operator, rather then the =.

For another thing, your algorithm would consider the number 143 to be prime, even though 143 = 11 * 13

You need keep track of all the prime numbers that you have already computed - add them to an array. Use that array to determine whether or not a new number that you are testing is prime.

Answer 3

It seems to me that you are jumping into the deep-end after deciding the kiddy-pool is too deep. The prime number project will be assignment 2 or 3 in most beginning programming classes, just after basic syntax is covered. Rather than help you with the algorithm (there are many good ones out there) I'm going to suggest that you attempt to learn syntax with the python shell before you write long programs, since debugging a line is easier than debugging an entire program. Here is what you wrote in a way that will actually run:

count = 4
n = 10                        #I'm starting you at 10 because your method 
                              #says that 2, 3, 5, and 7 are not prime
d = [2, 3, 4, 5, 6, 7, 8, 9]  #a list containing the ints you were dividing by

def cycle(n):                 #This is how you define a function
    for i in d:               #i will be each value in the list d
        if not n%i:           #this is equal to if n%i == 0
            return 0          #not prime (well, according to this anyway)
    return 1                  #prime

while count < 1000:
    count += cycle(n)         #adds the return from cycle to count
    n += 1

print n - 1

The answer is still incorrect because that is not how to test for a prime. But knowing a little syntax would at least get you that wrong answer, which is better than a lot of tracebacks.

(Also, I realize lists, for loops, and functions were not in the list of things you say you know.)

Answer 4

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...

Answer 5

To answer your subsequent question, 'How do I keep track of all the prime numbers?

One way of doing this is to make a list.

primeList = [] # initializes a list

Then, each time you test a number for whether it is prime or not, add that number to primeList

You can do this by using the 'append' function.

primeList.append( potprime )  # adds each prime number to that list

Then you will see the list filling up with numbers so after the first three primes it looks like this:

>>> primeList
[11, 13, 17]

Answer 6

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, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 93 and 97. 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]