### Poll & solutions

Nov. 11th, 2009 10:52 pm**elz**posting in

**intro_to_cs**

First:

Also, it occurs to me that it might be handy to have a place to post/discuss solutions to the problem sets, to see what we can learn from each other in the absence of TAs. If you actually go to MIT and the problem sets are still the same, don't read these. ;)

Fire away!

Open to:

**Registered Users**, detailed results viewable to:**All**, participants: 25Tickyboxes!

Also, it occurs to me that it might be handy to have a place to post/discuss solutions to the problem sets, to see what we can learn from each other in the absence of TAs. If you actually go to MIT and the problem sets are still the same, don't read these. ;)

Fire away!

## no subject

Date: 2009-11-12 04:14 am (UTC)elzEdited Date: 2009-11-12 04:15 am (UTC)## no subject

Date: 2009-11-12 06:32 am (UTC)gchick## no subject

Date: 2009-11-12 01:15 pm (UTC)elz(I actually don't know if I knew that about prime numbers at some point and had forgotten it, but I spent quite a few minutes going, "Wait, is that true? I think it might be! Let's see if it works.")

Also, I've been writing a lot of Ruby on Rails code, and it's possible I'm just used to using arrays for everything. :)

## no subject

Date: 2009-11-12 01:40 pm (UTC)gchicknodswhereas I looked at the divisibility-by-primes issue and decided to sacrifice the efficiency of *only* testing on primes in favor of the efficiency of not having to repeatedly call on the list comprehension functions (with the assumption that most composite numbers would be divisible by something *kinda* low and so wouldn't have to go through a ton of test iterations anyway). I'm now really curious to test further...Of course, that's for choosing the 1000th prime; if I were trying to find the umpty-billionth, I'd probably try to find a way that wasn't brute-forcing it at all, but I'd also be making a lot more money in something crypto-related!

## no subject

Date: 2009-11-12 03:10 pm (UTC)elzOf course, that's for choosing the 1000th prime; if I were trying to find the umpty-billionth, I'd probably try to find a way that wasn't brute-forcing it at all, but I'd also be making a lot more money in something crypto-related!Heh, yes indeed.

## no subject

Date: 2009-11-12 03:03 pm (UTC)elzungemmed. I succeeded in getting rid of the stored boolean and made the initial variable assignments a little less hackish. Hopefully. :)## no subject

Date: 2009-11-12 04:31 am (UTC)elzIt would be more efficient if I smushed them together, but I wanted to see if the first function would work. For, you know, all the times I need lists of prime numbers in my daily life. *g* I'm not totally sure why the ratio is significant, but it does get closer to 1.

## LMsxQgfQKZIYxQHrT

Date: 2012-05-03 01:18 pm (UTC)## no subject

Date: 2009-11-12 04:36 am (UTC)gchickAnd for problem 2:

Edited Date: 2009-11-12 04:38 am (UTC)## no subject

Date: 2009-11-12 05:48 am (UTC)ungemmedelz's, but I'm only checking factors up to the square root. (Since all factors above the square root are "balanced" by factors below it, if I haven't encountered any factors by the time I get to the square root I'm not going to encounter any.)Problem 1## no subject

Date: 2009-11-12 05:52 am (UTC)ungemmed## no subject

Date: 2009-11-12 06:18 am (UTC)badgerbag## no subject

Date: 2009-11-12 06:24 am (UTC)ungemmedme. o.O## no subject

Date: 2009-11-12 06:25 am (UTC)ungemmedProblem 2## no subject

Date: 2009-11-12 02:45 pm (UTC)elz## WzOvEpgUHNwG

Date: 2012-05-03 02:40 pm (UTC)## no subject

Date: 2009-11-12 06:17 am (UTC)badgerbag## no subject

Date: 2009-11-12 06:24 am (UTC)badgerbag## no subject

Date: 2009-11-12 06:47 am (UTC)exor674Yeah, this includes some weird-crazy optimizations >_<

## kUsOwOPPqqovUv

Date: 2012-05-03 09:49 am (UTC)## no subject

Date: 2009-11-12 08:17 pm (UTC)yhleeThen for Problem 1:

## no subject

Date: 2009-11-14 09:03 pm (UTC)luckykittyCould you also return True or False rather than 1 or 0, and then just test if is_prime is true? I guess it's six of one?

## no subject

Date: 2009-11-14 09:16 pm (UTC)yhleeI am a great believer in helper functions--they let me break down the problem into chunks. ^_^

## no subject

Date: 2009-11-12 08:18 pm (UTC)yhleeI'm sure this is inefficient, but there it is. :-/

## no subject

Date: 2009-11-14 08:55 pm (UTC)luckykittyIt's SO educational to see everyone's solutions--clearly I'm not a very efficient coder. Must learn! *determined*

## Problem 1a

Date: 2009-11-15 10:30 pm (UTC)quartzpebblefrom math import *

target_primes = 1000 #nth prime that we want to compute

current_no = 3

prime_counter = 2

i = 3

while prime_counter < target_primes:

prime_counter += 1

current_no += 2

i = 3

while i <= sqrt(current_no):

if current_no%i == 0:

current_no += 2

i = 3

else:

i += 2

print str(current_no) + " is the " + str(prime_counter) + "th prime."

(Now with better formatting here.)

## Not actually better formatting

Date: 2009-11-15 10:32 pm (UTC)quartzpebble## no subject

Date: 2009-11-16 02:29 am (UTC)zulu`#time 12:17 - 2:26`

# the 1000th prime is 541

poprime = 3 # start with 3 as the first potential prime to get 2 out of the way

counter = 1 # since 2 is prime start the iteration already at 1

while counter < 1000: # begin by checking how many iterations we're at

if (poprime/2)*2 == poprime: # if poprime is even

poprime = poprime + 1 # if poprime is even, add one and restart the iteration

elif poprime%2 > 0: # else if poprime is odd

factor = 2 # start factors at 2 because a prime is divisible by 1

while 1 < factor < 0.5*poprime: # all factors greater than half are mirrors

if poprime%factor == 0: # no remainder means it's divisible

poprime = poprime + 1 # not prime; increase poprime but not counter

factor = poprime # this should make the factor too big to get into this loop again

if poprime%factor > 0: # in this loop must check all factors

factor = factor + 1 # if one factor doesn't work, check the next

if factor >= 0.5*poprime: # when you've checked all the factors

if poprime%factor == 0: # no remainder means it's divisible

poprime = poprime + 1 #not prime; increase poprime not counter

if poprime%factor > 0: # You need to know that all your tests failed.

# But if you get out of your loops every time a test was true,

# then if your loops are good, then having checked all possible factors should be enough.

# This number is prime.

poprime = poprime + 1 # Increase poprime to check the next potential

counter = counter + 1 # You found a prime, so increase the counter.

poprime = poprime +1

if counter == 1000:

print poprime

This doesn't work, but it's based only on what we've been taught in the lectures and maybe some of the readings. I don't understand lists yet. I can't read the code in the answers upthread of mine--I was looking for things to reverse-engineer, but no such luck!

What is nice about this program is that by pure chance it'll give you 29 as the 10th prime if you set the counter to print at 10. It makes you feel all happy inside until you try it at different numbers!

Edited Date: 2009-11-16 02:41 am (UTC)## no subject

Date: 2009-11-16 04:26 am (UTC)zulu`#odds`

# This script will calculate the nth odd number

odd = 0

counter = 0

odds = []

print ("Let's find the nth odd number. Please enter a postive integer: ")

answer = raw_input()

nth = int(answer)

while counter < nth:

if odd % 2 == 0:

print str(odd) + (" is even. It doesn't go on the list.")

odd = odd + 1

print ("We have found ") + str(counter) +(" odd numbers. Let's keep going.")

elif odd % 2 != 0:

print str(odd) + " is odd. It goes on the list."

odds.append(odd)

if len(odds) == int(nth):

print ("The ") + str(nth) + ("th odd number is ") + str(odd)

break

else:

print ("We have found ") + str(len(odds)) +(" odd numbers. Let's keep going.")

odd = odd + 1

counter = counter + 1

Edited Date: 2009-11-16 04:28 am (UTC)## no subject

Date: 2009-11-16 06:27 am (UTC)zuluelz's inbox, where all my edited comments full of code probably ended up.`# primes`

# AKA sleep is for the weak

# This script will calculate the nth prime number

primes = [2] # This is a list called primes, and its first item is 2

counter = 1 # Because 2 is the first prime and your list already has 1 item.

print ("Let's find the nth prime number. Please enter a postive integer: ")

answer = raw_input()

nth = int(answer) # The user enters the answer N. To do math with the answer, you have to make it an integer.

prime = 3 # Start at 3 so you don't have to deal with the fact that 2 is the first prime.

while counter < nth: # Until you reach N, follow these instructions:

if nth == 2: # So you don't have to deal with 2 being the first prime

primes.append(3) # Make sure you keep your list up-to-date otherwise nothing else will work

print ("The ") + str(len(primes)) + ("nd prime number is 3.") # Concatenating strings & integers is fun!

break # I don't know if this is necessary, but it gets you out of the loop.

elif 2 < prime and prime % 2 == 0: # Here's where the real work starts. If the potential prime is even:

print str(prime) + (" is even. It doesn't go on the list.") # You don't go further.

print ("We have found ") + str(counter) + (" prime numbers. Let's keep going.")

prime = prime + 1 # Having dealt with one case, make sure you increase the iteration

elif 2 < prime and prime % 2 != 0: # If the potential prime is odd:

print str(prime) + (" is odd. Let's keep working with it.") # There's more to do.

factor = 2 # Start with a factor of 2 because primes are divisible by 1.

while factor <= prime*0.5: # Once you get to half the number, the rest of the factors are mirrors.

if prime % factor == 0: # If it's divisible...

print str(prime) + (" has a factor. It is not prime.")

prime = prime + 1 # Increase the iteration but not the count of prime numbers

# (You haven't found any prime numbers yet.)

break

elif prime % factor > 0: # If it's not divisible...

print str(factor) + (" is not a factor. Let's keep going.")

factor = factor + 1 # You've tried one factor, now try the next.

if factor > prime*0.5: # You need to know that all your tests failed.

# But if you get out of your loops every time a test was true,

# then if your loops are good,

# so having checked all possible factors should be enough.

primes.append(prime) # You have found a prime number! Add it to your list.

if len(primes) == int(nth) and len(primes) == 3: # If you've reached N, print it out.

print ("The ") + str(len(primes)) + ("rd prime number is ") + str(prime) # This is just fancy to get the ordinal correct.

break

if len(primes) == int(nth): # If the number of items on your list is equal to N, then stop.

print ("The ") + str(nth) + ("th prime number is ") + str(prime)

break

else: # If you haven't reached N, keep going.

print ("We have found ") + str(len(primes)) +(" prime numbers. Let's keep going.")

prime = prime + 1 # Increase the potential prime by one.

counter = counter + 1 # Since you've found a prime, increase the count by one.

if nth == 1:

print ("The 1st prime number is 2.") # This helps deal with users who enter 1 as N. (Very funny, users. Not.)

if nth == 1000: # To shorten the program run time, comment out all that printing and just leave this one.

print ("The ") + str(nth) + ("th prime number is ") + str(prime)

Edited Date: 2009-11-16 06:32 am (UTC)## no subject

Date: 2009-11-16 09:10 am (UTC)tassosss#Initialization of terms

Number = 3 #lowest odd prime

primeCounter = 2 #inclusive of 2 and 3

Test = 3 #lowest possible factor for odd numbers

while(primeCounter < 1000):

while(Test < Number):

if Number%Test > 0: #checks to see if number is divisible by anything

Test = Test + 2 #if it is not then tries the next odd number

else: Test = Number + 1 #if it is divisible then it halts the loop

if Test == Number: #test can only reach the number if it is non divisible

primeCounter = primeCounter+1 #so the prime counter goes up

Number = Number + 2 #number goes to next odd number

Test = 3 #test is reset to lowest potential odd factor

print 'The', primeCounter,'th prime is' #final result is printed

Number = Number - 2

print Number

eta - I have no idea how to get the indents to show up.

Problem 2 tomorrow.

Edited Date: 2009-11-16 09:15 am (UTC)## no subject

Date: 2009-11-17 01:49 am (UTC)zuluAre there any readings that go along with this week that might help?

Here's my test case:

`from math import *`

number = log(2)

print number # this works

primes = (2, 3, 5, 7, 11, 13) # this is just as a test case

number = 6

sum = sum(log(primes)) # this is where I get an error message

print sum

ratio = sum/number

print ratio

## no subject

Date: 2009-11-19 05:35 am (UTC)bellerina## no subject

Date: 2009-11-19 03:33 pm (UTC)zulu## no subject

Date: 2009-11-19 05:47 am (UTC)bellerinaMy solutions also seem a little clunky, but I guess they work...

My solution for problem 1:

count = 2

numb = 3

n = int(raw_input("What prime are you trying to find?"))

while(count<=n):

i = 2

isprime = 1

half = numb/2

while(isprime > 0 and i < half):

if numb%i != 0:

i = i+1

else:

isprime = isprime-1

if isprime == 1:

if count < n:

count = count + 1

numb = numb + 2

else: break

else:

if count <= n:

numb = numb + 2

print numb,"is prime number",count

My solution for problem 2:

from math import *

n = int(raw_input("What number?"))

logprimes = [log(2)]

numb = 3

while(numb<=n):

i = 2

isprime = 1

root = sqrt(numb)

while(isprime>0 and i<=root):

if numb%i != 0:

i = i+1

else:

isprime = isprime-1

if isprime == 1:

logprimes.append(log(numb))

if numb < n:

numb = numb + 2

else: break

else:

if numb <= n:

numb = numb + 2

print "The sum of the logs is",sum(logprimes)

print "The number is",n

print "The ratio of the sum and n is",sum(logprimes)/n

## no subject

Date: 2009-11-19 07:12 pm (UTC)erdaHere are mine. I stuck to while and if statements, since those are about the the only things I understand so far.

Problem 1:

count=2 #keeps track of which prime number we are at, assume 2 is the first prime

candidate=3 #the number we are checking to see if it is prime

test_divisor=3 #the number we are dividing by

while count<1001: #program will continue until we reach the 1000th prime

while candidate>=(test_divisor*test_divisor): #we can stop dividing when the divisor gets bigger than the square root of our candidate

remainder=candidate%test_divisor

if remainder==0: #if there is no remainder, the number is not prime so we will go to the next candidate

candidate+=2 #only odd numbers need to be checked

test_divisor=3 #must reset this for next candidate

else:test_divisor+=2 #if there is a remainder we will try the next divisor, no need to use even divisors

count+=1

test_divisor=3

candidate+=2

print "The 1000th prime number is", candidate-2

Problem 2:

from math import *

n=input("What number do you want to stop at?")

candidate=3 #the number we are checking to see if it is prime

test_divisor=3 #the number we are dividing by

OldLog=log(2)

while candidate<=n: #program will continue until we reach the input number

while candidate>=(test_divisor*test_divisor): #we can stop dividing when the divisor gets bigger than the square root of our candidate

remainder=candidate%test_divisor

if remainder==0: #if there is no remainder, the number is not prime so we will go to the next candidate

candidate+=2

test_divisor=3 #must reset this for next candidate

else:test_divisor+=2 #if there is a remainder we will try the next divisor

NewLog=OldLog + log(candidate)

OldLog=NewLog

test_divisor=3

candidate+=2

print "Your number is", n

print "The sum is", OldLog

print "The ratio of the sum to your number is", OldLog/n

## no subject

Date: 2009-11-20 03:35 pm (UTC)medrin1a)

1b)