Question

wanderboy: In the solution to problem set 1 I get some numbers in the calculations that are not primes. What do I do wrong?

The code is listed below
http://codepad.org/7uua2c5w

Answer 1

There is a problem with your code , you make it go through the numbers from 1 to the number that you are checking if it's prime or not , if it is not divisible by ONE OF THE numbers in this range , then you make it a prime although this is not right ! You should make sure it is not divisible by each number in this range to add it to the prime list

Answer 2

And don't start dividing by 1, since every number is divisible by 1.

Answer 3

OK,
here's the new code. I have guessed a little bit so I would appreciate some help in explaining the following lines to see whether my thoughts are correct:
My interest is pointed toward lines 4-6 and 9-13 of the following solution:
http://codepad.org/d9RSbJoy
According to my understanding I am initiating a loop in line 4 """while itersLeft>0:""" and initialising a divisor """divisor=2""" inside that loop whith which every calculation inside that loop is going to start.
Later inside that loop in line 6 I am initiating a second loop """while (x>divisor):""" inside the first one therefore limiting the increase of the divisor and then in line 9 placing a condition that in case that the variable x in not evenly divided to divisor """ if x%divisor!=0:""" then the divisor has to increase its value by one """divisor=divisor+1""". What I am not sure here is whether after the first check the divisor is going to be increased only once or is it going to be increased multiple times until it reaches the value of the variable x due to the loop """while (x>divisor):""" initiated in line 6.
The second question that I have is whether the divisor is starting with the value of 2 as it it is initiated with that value inside the loop and every time after finishing of line 14 the calculation is going back to line 4 to continue the while loop until the condition """while itersLeft>0:""" is fulfilled and therefore starting with a value of 2 for the divisor. Please correct me if I am wrong. Any explanation is welcome.

Answer 4

you are getting numbers that aren't prime.
where do you decide that a number is prime?
at line 10 - where you add x to the tuple primes
line 10 must be at the wrong place

when do you know a number is prime?
- when it can't be evenly divided by ANY of the divisors in the for loop

a useful debugging technique is to put print statements in your code and print variables, results of calculations, results of tests .... it lets you see what is happening as it is executing.
something like this http://codepad.org/9lW86a9A

and as mentioned above, you want to start your for loop at 2 not 1.

Answer 5

bwCA,
I guess you are talking about my first attempt. Thank you for your debugging technique. As I feel unconfident now about that first attempt since I feel I lack some knowledge about range /I can not create a model to check all the numbers in the range - I thought that I am testing all the values of divisor while it appears to only test one/. I am interested to find a solution with the range command but as I need some more knowledge I have tried a bypass model with 2 while loops and an if condition /please see my second attempt in my second post/. Any comments on the improvement of the first or the second attempt are welcome.

Answer 6

the docs should be on your computer - if using windows and idle, F1 from within idle
http://docs.python.org/library/functions.html#range

nothing wrong with how you used range in your first post, you are just adding a number to the primes tuple to early. you shouldn't add the number to the primes tuple till after you have tested it with all the divisors in the for loop. --> you should add the number to the primes tuple after the for loop has finished (if it passed the prime test for all divisors)
http://docs.python.org/reference/compound_stmts.html#the-for-statement

Answer 7

maybe write down in words what you want to do
something like

start with x = 3
while the number of primes found < 1000 (or 998)
assume x is prime
start testing with divisor = 2
while divisor is less than the square root of x
test x with divisor:
if it is evenly divisible
x is not prime
stop testing
if it is not evenly divisible
# x might be prime
increment divisor to continue testing
if x has been tested by every divisor (less than square root of x) and passed
add x to the tuple primes
increment x by 2

Answer 8

OK,
here's the new attempt /taking into account the pointers of bwCA/:
http://codepad.org/SBnDNpuS .
I am using a different way of checking for the primes which I guess is supposed to reduce the processor time/optimization/ as I believe I am reducing the number of calculations.
Also I am using a new and unknown to me until this moment function - break as I could not find another way to cancel the loop /process/ if the number is not prime. If there is a better way to do it please point it.
So far I could not manage to do the calculation with range function. Perhaps I am missing something here.
Please feel free to share any thoughts that you may have on the above.

Answer 9

1 is not a prime number. Print up to 997 instead of 996 and see if you get 7919, which I believe is the correct answer. Instead of break, make the variable go outside the parameters of the condition of the while loop (i.e. if loop says while x>0, then break out of the loop by saying x==0(instead of break) if a certain condition is fulfilled.

Answer 10

Hi wanderboy, so I think your code is fine, nothing wrong with using the break function. Only you are missing the last prime which should be 7919, when your code is returning 7907, basically print primes[iterations]. Some advice to reduce processing time:
1.) you can start the divisor at 3, and increase by two each time, no point checking even numbers
2.) you can just use the list of primes that you make and see if they are factors because we know a number is prime if it cannot be broken down into a series of prime e.g. 36 = 2^2 * 3^3
3.) rather than cap it at half, you can consider the divisors you check at sqrt(prime)

Answer 11

Joe Coale,
after the correction I've got 7919:
http://codepad.org/vhD5dI1f

jliu,
here's the second variant:
http://codepad.org/mm8g9Lgx

The only thing left here I believe is to make it with the elusive so far range function as tried in the first post. Any suggestions?

Answer 12

http://docs.python.org/reference/compound_stmts.html#the-while-statement
http://docs.python.org/library/functions.html#range
http://dpaste.com/703522/

the docs should be on your computer also. F1 from within idle/windows
I find the docs on my computer easier to use than the on-line version

Answer 13

OK, here's the for in range solution:
http://codepad.org/mm8g9Lgx
Any thoughts or comments - please feel free to share.

Answer 14

so what about problem 2 ? did you solve it wanderboy ?

Answer 15

Not yet.
I am quite busy currently.