Question

how is pset1 problem 1 done? i have spent a little bit of time on it nd i cant figure out were im going wrong.

Answer 1

Feel free to paste any/all the code you've got so far to dpaste.com, then submit the url here for the code so we can review it and try to help.

In general terms, you will want some process for identifying if a given number is a prime number, and then you need to loop over all the numbers, from 2 (or 3) on, performing that 'prime test' process on each of them until you have found 1000 of them that pass the test.

Answer 2

I'm also having trouble with problem 1. Here is my code so far:

http://dpaste.com/512919/

My method was to divide all odd integers by every integer divisor that is less than or equal to half the number being tested. This should filter out all non-prime numbers, but for some reason it is including some numbers that are not prime. I had it print all the numbers so I could see if there was some sort of pattern to the error, and it seems to be returning some (but not all) numbers that are multiples of primes. For example: 121 (11*11), 209 (11*19), 221 (13*17), 305 (5*61), and 323 (17*19) are the first several non-primes it included. I can't seem to figure out what's wrong with the code. Any help would be greatly appreciated.

Answer 3

After reading some of the other comments and racking my brain for a while, I finally figured it out! Here is my new code for anyone else who might be having a similar problem:

http://dpaste.com/513193/

I changed the variable names and added comments so it would make more sense to readers, but the only change I needed to make to the actual code was adding line 8, which resets the divisor when the number is changed. I also eliminated the 'remainder' and 'result' variables because they were unnecessary.

Answer 4

That certainly works, though this solution is very tightly coupled. By this I mean that the code which searches for possible divisors also moves the process along to the next prime when it finds one. The result is that it is very difficult to reuse this code for any other task. An alternative solution is to write a piece of code which will test a single number for primeness, then simply wrap that code in a loop which iterates all the odd numbers testing each in turn. In this way you could re-use your test code in other situations where you needed to know if a given number was prime or not.

I do have to commend you on your efforts in debugging the code and finding the flaw in your original version though. Those kinds of bugs can be very hard to track down.

Answer 5

Thanks for the feedback, Polpak! Here is my new code based on your suggestion:

http://dpaste.com/521985/

I moved the "test_number=test_number+2" line outside the while-loop that tests for primeness and to the beginning of the prime_counter while-loop. Does this make it less tightly coupled?