You are currently browsing the daily archive for January 3, 2010.

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

## Recent Comments