owl: text editor with code, captioned "life would be easier if I had the source code" (source code)
only a sinner saved by grace ([personal profile] owl) wrote in [community profile] intro_to_cs 2010-01-18 11:35 pm (UTC)

Here's my version. I decided to store the primes I'd already calculated in a list and use them as the divisors for the next candidate, rather than determining the divisors each time through the loop. Python's high-level, I imagine its list implementation is efficient enough for me not to worry about it :)
A number can't have a factor that's greater than its square root, so if it has reached that point, it's a prime and the control can break out of the loop.

#Problem 1
primes = [2] #list of primes. We know that 2 is the first prime
integer = 3 #so start checking at 3

while len(primes) < 1000:
   for p in primes: #we want to divide the candidate integer by all the primes we already have
       is_prime = 1 #we'll assume it's prime until proven otherwise
           if (integer % p == 0):
	       is_prime = 0 #if it can be divided equally by a prime, it's not prime
	       break        #so break out of the loop here
	   if p*p >= integer:
		break #don't keep checking with divisors greater than the square root
    if is_prime: #stopped dividing; is it prime?
        primes.append(integer) #add it to the array of primes
    integer = integer + 1 #and then move on to the next integer
#we're out of the while loop, so print the last prime, 
#and let's check how many we have while we're at it
print "The %dth prime is: %d" %(len(primes), primes[len(primes)-1]) #Don't forget the list is 
#zero-indexed, or we'll get a lovely index out of bounds error here


And the slightly adapted version for the second problem:
from math import *
n = int(raw_input("Enter a number: ")) #ask the user what is n
primes = [2] #list of primes. We know that 2 is the first prime
integer = 3 #so start checking at 3
sum_logs = log(2) #the log of the primes we have so far

while len(primes) < n:
    for p in primes: #we want to divide the candidate integer by all the primes we already have
        is_prime = 1 #we'll assume it's prime until proven otherwise
            if (integer % p == 0):
        is_prime = 0 #if it can be divided equally by a prime, it's not prime
        break        #so break out of the loop here
        if p*p >= integer:
            break #don't keep checking with divisors greater than the square root
     if is_prime: #stopped dividing; is it prime?
        primes.append(integer) #add it to the array of primes
        sum_logs = sum_logs + log(integer) #find the log and add it to the total
    integer = integer + 1 #and then move on to the next integer
#print out the sum of the logs, and the ratio
print "The sum of the logs of the first",len(primes), "primes is",sum_logs
print "The ratio of the sum to",n,"equals",(sum_logs / n)



I don't think I've put so many comments in code since I was in first year of uni ;)
You might also notice that I like to put double quotes around strings, and have a space on each side of the operators. I just think it's easier to read that way.

Post a comment in response:

This community only allows commenting by members. You may comment here if you're a member of intro_to_cs.
(will be screened if not on Access List)
(will be screened if not on Access List)
If you don't have an account you can create one now.
HTML doesn't work in the subject.
More info about formatting