intro_to_cs | Solution to ps1

The solution I wrote is behind the cut. Please let me know if you have any questions about the math or the code itself, or feel free to share your own solution in the comments.

# ps1 for MIT OpenCourse 6.00 Introduction to Computing
# Written by Jetamors, January 2010

# Problem 1: compute and print the 1000th prime number

# Remember that a prime number is an integer (whole number) that is not evenly divisible by any integer
# other than itself and 1. Therefore, my strategy is to divide every number bigger than 2 by all the integers smaller
# than it, except 1. For example, the number 5 would be divided by 4, 3, and 2.
# If every division gives me a remainder, then the number is prime; if even one remainder is zero, then the
# number cannot be prime.
#
# There are two things I did to simplify this problem:
# 1. Every even number bigger than 2 cannot be a prime number; therefore I stripped out all the prime numbers.
# 2. A number can't be evenly divisible by any integer more than half its size. For example, the biggest number you can
# evenly divide 10 by is 5. (I'm not really sure how to explain the math behind this, but if you test it it'll be
# true.) Therefore, I don't bother dividing a potential prime number by any number more than half its size.
# You don't have to do either of these things, but your code will take much longer to run if you don't do them. This code
# could be made to run even faster by immediately going to the next candidate as soon as you get a zero remainder,
# but... I didn't do that, oh well.

print 'Problem 1:'
primeiter = 1 # This counts the number of primes. We initialize this to 1 to account for the prime number 2.
candidate = 2 # This is the variable we use for each candidate for prime number. This is initialized to 2 so the first number
# the while loop evaluates will be 3.

while (primeiter<1000):
candidate = candidate + 1 # increment at the beginning so the last number won't be incremented
# print 'Current iteration is',candidate
remaindercheck = 1 # this is the variable we use when evaluating remainders
if (candidate/2)*2 != candidate: # this strips out all the even numbers
for i in range(3,candidate/2): # this strips out all the numbers bigger than 1/2.
remaindercheck = remaindercheck * candidate%i # This number is only non-zero if every remainder is non-zero.
# print remaindercheck
if remaindercheck != 0:
# print 'Prime number is',candidate
primeiter = primeiter + 1 # increment this every time we see a prime number

# printing the output
print 'The 1000th prime number is', candidate
print ' '

# Problem 2: compute the sum of the logarithms of all the primes from 2 to some number n.
# Print out the sum of the logs of the primes, the number n, and the ratio of these two quantities.

# Here, I modified the code from problem 1. The major difference is in the while loop. Before, the
# while loop continued until we reached the 1000th prime number. Now, we want the loop to continue until
# n is reached. Notice also that we add the log of a number only if it's a prime number.

print 'Problem 2:'
from math import * # so we can use the log function
candidate = 2
logprimesum = log(2) # this initalizes the sum of the logs with the log of the prime number 2.
n = int(raw_input('Please enter a number! '))

while (candidate<=n): # note that the while statement has changed; now it's based on n, not the number of primes.
candidate = candidate + 1
remaindercheck = 1
if (candidate/2)*2 != candidate:
for i in range(3,candidate/2):
remaindercheck = remaindercheck * candidate%i
if remaindercheck != 0:
logprimesum = logprimesum + log(candidate)

# printing the output
print ' '
print 'The sum of the logs of the prime numbers from 2 to',n,'is',logprimesum
print 'The ratio of that sum to',n,'is',logprimesum/n