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]

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.