Question

ps1b. I've written code to solve ps1b. It is terribly inefficient and it doesn't do exactly what I thought it would do (however, it kind of gets the job done). If you were to answer from the stand point of correcting the existing code, what would you say to the following:
Can someone explain why the code prints the last 11 primes through the 999th, instead of just the 999th prime? http://codepad.org/rTVajM1t
The code gets a time out in codepad, but will run locally. Thank you!

Answer 1

hey - good code but have a few comments. So, the code is printing answers for all numbers between the 999th and 1000th prime, including the 1000th prime itself. These 11 numbers - not primes - are printed before the last prime because your counter only increases when you reach a prime number and you have the print statements conditioned upon what the counter is at. So, count == 999 for a while before you reach the 1001th prime.

Regarding the efficiency concern you have, there are two things I think you could do to cut down on run time. First, you don't need to check if the primes will be divisible by even numbers, because they are all odd (cept for good ol'2). Secondly, you don't need to check every number between 2 and the number itself - you only have to check from 3 to (n+1)/2. If a number is factorable into the product of two numbers, one of these will be in the lower half of the range of numbers between 0 and the number itself, and one in the upper half of this. So, if you've checked all of the lower half, then you have also checked all of the upper half.

My last observation is not about efficiency of the code. It doesn't look like your code will be able to stop at non-prime numbers, because the while loop doesn't terminate until the nearest prime is reached. (In this case, you have it set to the 1000th prime.) So, there currently isn't an easy way to check what the ratio of, say, 458 to the sum of the logs of primes less than it is. You'd have to guess the number of primes less than 458 and put that in the count < (some number) part until you got close enough. This can be solved pretty easily I think, but wanted to flag this concern for you.

I hope this helps / thanks for posting!!

Answer 2

ps1b is a very good problem to work through in detail and carefully. You will learn a lot about computation from its study. When I look at your code it seems muddled and, therefore, you don't get result that you are looking for. I recommend breaking the problem into a series of smaller problems. The first "smaller" problem I recommend you write code for is the following:

If I give you an integer n, can you calculate the nth prime?

For example, if I input the number 5 your program return back the number 11 since it is the 5th prime. Similarly, if I input 10 as n the program would return back the number 29, since it is the 10th prime.

A bonus will be if you can write a function to calculate the nth prime. The function would take n as the argument and return the nth prime. The advantage of writing a function is to achieve modularity. You can then re-use the code in other program, including as you build up to ps1b.

Here is a list of the first 1000 prime numbers so you can verify that your program is working correctly:

http://primes.utm.edu/lists/small/1000.txt

You will need to solve this smaller problem if you want to unpack and solve ps1b.

Answer 3

Thank you swdalb and malpaso! I'm going to take your advice and spend a little time developing better solutions for ps1a and ps1b. I look forward to feedback when I get it cleaned up a little. Thanks again!