### Solution to ps1

Jan. 16th, 2010 01:59 am**jetamors**posting in

**intro_to_cs**

The solution I wrote is behind the cut. Please let me know if you have any questions about the math or the code itself, or feel free to share your own solution in the comments.

# ps1 for MIT OpenCourse 6.00 Introduction to Computing # Written by Jetamors, January 2010 # Problem 1: compute and print the 1000th prime number # Remember that a prime number is an integer (whole number) that is not evenly divisible by any integer # other than itself and 1. Therefore, my strategy is to divide every number bigger than 2 by all the integers smaller # than it, except 1. For example, the number 5 would be divided by 4, 3, and 2. # If every division gives me a remainder, then the number is prime; if even one remainder is zero, then the # number cannot be prime. # # There are two things I did to simplify this problem: # 1. Every even number bigger than 2 cannot be a prime number; therefore I stripped out all the prime numbers. # 2. A number can't be evenly divisible by any integer more than half its size. For example, the biggest number you can # evenly divide 10 by is 5. (I'm not really sure how to explain the math behind this, but if you test it it'll be # true.) Therefore, I don't bother dividing a potential prime number by any number more than half its size. # You don't have to do either of these things, but your code will take much longer to run if you don't do them. This code # could be made to run even faster by immediately going to the next candidate as soon as you get a zero remainder, # but... I didn't do that, oh well. print 'Problem 1:' primeiter = 1 # This counts the number of primes. We initialize this to 1 to account for the prime number 2. candidate = 2 # This is the variable we use for each candidate for prime number. This is initialized to 2 so the first number # the while loop evaluates will be 3. while (primeiter<1000): candidate = candidate + 1 # increment at the beginning so the last number won't be incremented # print 'Current iteration is',candidate remaindercheck = 1 # this is the variable we use when evaluating remainders if (candidate/2)*2 != candidate: # this strips out all the even numbers for i in range(3,candidate/2): # this strips out all the numbers bigger than 1/2. remaindercheck = remaindercheck * candidate%i # This number is only non-zero if every remainder is non-zero. # print remaindercheck if remaindercheck != 0: # print 'Prime number is',candidate primeiter = primeiter + 1 # increment this every time we see a prime number # printing the output print 'The 1000th prime number is', candidate print ' ' # Problem 2: compute the sum of the logarithms of all the primes from 2 to some number n. # Print out the sum of the logs of the primes, the number n, and the ratio of these two quantities. # Here, I modified the code from problem 1. The major difference is in the while loop. Before, the # while loop continued until we reached the 1000th prime number. Now, we want the loop to continue until # n is reached. Notice also that we add the log of a number only if it's a prime number. print 'Problem 2:' from math import * # so we can use the log function candidate = 2 logprimesum = log(2) # this initalizes the sum of the logs with the log of the prime number 2. n = int(raw_input('Please enter a number! ')) while (candidate<=n): # note that the while statement has changed; now it's based on n, not the number of primes. candidate = candidate + 1 remaindercheck = 1 if (candidate/2)*2 != candidate: for i in range(3,candidate/2): remaindercheck = remaindercheck * candidate%i if remaindercheck != 0: logprimesum = logprimesum + log(candidate) # printing the output print ' ' print 'The sum of the logs of the prime numbers from 2 to',n,'is',logprimesum print 'The ratio of that sum to',n,'is',logprimesum/n

## no subject

Date: 2010-01-16 10:33 pm (UTC)winterthunderReading through this, I'm following you up until this line: remaindercheck = remaindercheck * candidate%i

If I've understood correctly, this is the line that divides the number by all the numbers less than it, right? How exactly is it doing that?

## no subject

Date: 2010-01-17 12:10 am (UTC)jetamorsIn case a little extra explanation is needed: a for loop is a specific kind of while statement. It increments the variable i from 1 to candidate/2, and then it finishes. (Generally speaking, I've been taught that it's better to use for loops where you can; a for loop is guaranteed to end at some point, but an incorrectly written while loop can loop infinitely.)

i is the number I'm going to be dividing candidate by. The statement candidate%i returns the remainder of candidate/i; so for example, if candidate = 5 and i = 3, then candidate%i = 2, because 5/3 = 1 and 2/3.

For the statement

remaindercheck = remaindercheck * candidate%i, I'm taking advantage of the fact that any number multiplied by zero is equal to zero. What this means is that if any remainder is equal to zero, then remaindercheck will be set to zero until the end of the for loop. If none of the remainders are zero, then remaindercheck will be some positive number.For example:

if candidate = 9:

when i = 3: remainder of 9/3 = 0, therefore remaindercheck = 1 * 0 = 0

when i = 4: remainder of 9/4 = 1, therefore remaindercheck = 0 * 1 = 0

When the for loop ends, remaindercheck = 0 and we know this is not a prime number.

if candidate = 11:

when i = 3: remainder of 11/3 = 2, therefore remaindercheck = 1 * 2 = 2

when i = 4: remainder of 11/4 = 3, therefore remaindercheck = 2 * 3 = 6

when i = 5: remainder of 11/5 = 1, therefore remaindercheck = 6 * 1 = 6

When the for loop ends, remaindercheck != 0 and we know this is a prime number.

Does that make sense?

## no subject

Date: 2010-01-17 12:43 am (UTC)winterthunderAre you defining i in the line: for i in range(3,candidate/2)?

Thanks so much for posting and being willing to explain!

## no subject

Date: 2010-01-17 01:52 am (UTC)jetamorsYes, that's correct. If it helps, here's a while loop that would give exactly the same result as my for loop:

Let me know if you have any other questions or want me to explain something in a different way. It's so hard to explain math when we can't talk face to face >.<

## no subject

Date: 2010-01-17 02:31 am (UTC)winterthunderYeah, I'm pretty sure at least half of my issues with this is the math; I got through AP Calc BC by the skin of my teeth in high school, six years ago, and I haven't looked at anything other than statistics since then. Thank you again!

## no subject

Date: 2010-01-17 12:27 am (UTC)jetamorsfindour largest integer: the 1000th prime number.You could probably kludge it by getting, say, every prime number between 1 and 10,000 and then hoping that the 1000th prime is in there. But that would be pretty inefficient.

## no subject

Date: 2010-01-17 12:51 am (UTC)winterthunder## no subject

Date: 2010-01-17 02:01 am (UTC)jetamorsIf we used your approach with a finite list, though, it would still work: for example, you could take the numbers from 1 to 10,000 and sieve out all the non-primes. You'd be left with more than 1000 prime numbers, so you could just print the 1000th. It's not how I would do it personally, but the cool thing about programming is that even for simple problems like this, different people will write very different programs to solve them. There's more personal style in it than you might think :)

## no subject

Date: 2010-01-17 11:45 pm (UTC)arantheSince primes require so much computing power, I tried to close down the number of candidates and tests as much as I could. To do that, I did three things:

`break`

keyword to exit the loop as soon as a candidate number was weeded out.It runs pretty fast; here are the stats:

I'd love to see if I could improve on that, but I'm really out of time this week.

## no subject

Date: 2010-01-18 01:21 am (UTC)jetamors## no subject

Date: 2010-01-18 11:35 pm (UTC)owlA 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.

And the slightly adapted version for the second problem:

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.

Edited (whitespace fail) Date: 2010-01-18 11:49 pm (UTC)## no subject

Date: 2010-01-19 05:05 am (UTC)jetamorsbetween1 and n, not n number of primes. If you do it that way, the ratio you get should always be between 0 and 1.## no subject

Date: 2010-01-19 11:43 pm (UTC)owl`while len(primes) < n:`

to`while integer <= n:`

that should do the trick.## no subject

Date: 2010-01-19 11:51 pm (UTC)arantheVery elegant! Since I used the same basic logic outline, I merged our approaches: Used your square root limit with my increment of 2 and knocked about another 4000 tests off. Cool!