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

[elz]

Okay, this is a little rough, but I'm still at the point where I'm happy that it's a) in Python and b) runs. For the first question:

# Returns the requested prime number
def find_nth_prime(prime_to_find):
    n = 3
    primes = [2]
    print "%i is prime number #%i" % (primes[0], len(primes))
    while len(primes) < prime_to_find:
        n_is_prime = True
        for prime in primes:
            n_is_prime = (n%prime != 0)
            if n_is_prime is False:
                break
        if n_is_prime:
            primes = primes + [n]
            print "%i is prime number #%i" % (n, len(primes))
        n = n + 2
    return primes[prime_to_find - 1]
    
prime_to_find = int(raw_input('Which prime number would you like to find?\n'))
find_nth_prime(prime_to_find)

[gchick]

Out of curiosity, what was your reason for using a list? Given that the requirement was to return a final value, why go to the trouble of storing and retrieving the intermediate ones?

[elz]

Because every non-prime number is divisible by at least one prime number, so I figured I could save a lot of iterations by storing the numbers I knew to be prime and only checking new numbers against those.

(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. :)

[gchick]

nods whereas 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!

[elz]

Yeah, the trade-offs in speed and overhead of different approaches - that's one of the things I really, really want to understand better.

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!

Heh, yes indeed.

[elz]

Okay, here's my slept-on-it version, with bonus wisdom gleaned from ungemmed. I succeeded in getting rid of the stored boolean and made the initial variable assignments a little less hackish. Hopefully. :)

def find_nth_prime(prime_to_find):
    n = 1
    primes = []
    if prime_to_find < 1:
        print "Please enter a number greater than zero."
        return None
    else:
        while len(primes) < prime_to_find:
            if len(primes) == 0:
                primes.append(2)
                print "%i is prime number #%i" % (primes[0], len(primes))
            else:
                root = math.sqrt(n)
                for prime in primes:
                    if n%prime == 0:
                        break                
                    elif prime > root:
                        primes.append(n)
                        print "%i is prime number #%i" % (n, len(primes))
                        break
            n = n + 2
        return primes[prime_to_find - 1]