Poll & solutions

[elz]

First:

Poll #1689

Open to: Registered Users, detailed results viewable to: All, participants: 25

View Respondents

Tickyboxes!

View Answers

Finished lecture 2
24 (96.0%)

Finished problem set 1
15 (60.0%)

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!

Comments

[ungemmed]

Here are mine! They're a lot like elz'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

import math

primes = [2]
x = 3
while len(primes) < 1000:
    divisible = False
    root = math.sqrt(x)
    for y in primes:
        if x % y == 0:
            divisible = True
            break
        if y > root:
            break
    if not divisible:
        print x
        primes.append(x)
    x += 2

[ungemmed]

argh, Dreamwidth keeps on choking on my solution for problem 2! I guess it's reading the code as some malicious hacking attempt or something.

[badgerbag]

try wrapping it in

  or  tags maybe...

[ungemmed]

Thanks! It actually turned out, though, that NoScript was being overzealous and thought Dreamwidth was trying to hack me. o.O

[ungemmed]

Problem 2

import math

n = int(raw_input('n? '))

primes = [2]
x = 3
logs = 0
while x <= n:
    divisible = False
    root = math.sqrt(x)
    for y in primes:
        if x % y == 0:
            divisible = True
            break
        if y > root:
            break
    if not divisible:
        logs += math.log(x)
        primes.append(x)
    x += 2
print logs
print logs / n

[elz]

Aha! I was going to stop at the square root, but then I started overthinking it. And I was looking for something like the append method, but I couldn't figure out what it was called.

WzOvEpgUHNwG

[(Anonymous)]

Well, I actually know two pforos: one leads to a very quick solution but requires the knowledge of some number theory. The other proof works on first principles but leads to a much longer computation. I was assuming most readers would find the second one.