I’ve decided to take the MIT OpenCourseWare class 6-00 Introduction to Computer Science and Programming. I know, I know, it’s an intro class, but it looks like fun. That and I’ve never programmed in python before, which is the language taught in this course. So, I’m going to learn Python for fun. It’s amazing how quickly the language can be picked up. Here is my first real attempt at writing in the language. Other than a couple of test “hello world” type things to get a better grip on the syntax.

 So, the first real problem given out is to write a program to find the 1000th prime number.  So, here is my first go round. It’s not very elegant, or algorithmically pretty, but it brute forces the correct answer out to at least 10,000 prime numbers. I checked.

# Write a program that computes and prints the 1000th prime number

# initialize some variables
# generate odd integers
# check to see if it’s a prime number
# use a%b to get remainder and see if it equals zero
# Note, we count 1 as a prime instead of 2 just to make this easier to code.
# 2 is an even number and messing with the logic. It’s a cheat, I know.

count = 1
candidate = 1
while count <= 1000:                         # iterate until 1000 primes found
    myresult = ‘prime’                            # turn on prime found flag
    half = candidate / 2                         # set the half way point
    iterator = 3                                       # start dividing with 3

    while iterator <= half :
        if candidate % iterator == 0 :  # do we have a divider?
            myresult = ‘notprime’           # turn off prime found flag
            iterator = half + 1                 # Stop counting we found a divider
           
        iterator = iterator + 2

    if myresult == ‘prime’ :
        count = count + 1                        # found a prime, iterate the counter
       
    candidate = candidate + 2             # set candidate to next odd number

# Print out 1,000th Prime Number   
print ‘The’,count – 1,’th prime is ‘, candidate – 2

 And in case you are wondering the answer is
The 1000th prime is  7919

Advertisements