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.
no subject
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 hereAnd 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.