Can anyone debug a python script for me?

[Phat Pat]

supposed to find primes, but I'm not getting any output, and I dont know why.
I'm relatively new to python, so I thout I'd make a simple program to try it out, but I get nothing, x is stuck on the input value and y is stuck at 2.

begin = input("Start at what number? ")
max = input("Stop at what number? ")

test1 = begin % 2
if test1==0:
    begin = begin + 1
x = begin
import math
while x < max:
    xsqrt = math.sqrt(x)
    xsqrtr = round(xsqrt,0)
    y = 2
    while y < xsqrtr:
        test2 = x % y
        if test2==0:
            x = x + 2
            break
        if y==xsqrtr:
            print x
        y = y + 1

[Gizmo]

What are your input values for testing?

[Phat Pat]

Originally Posted by gizmo

What are your input values for testing?

here is what I get from the python shell

>>> 
Start at what number? 2
Stop at what number? 20

Traceback (most recent call last):
  File "C:\Documents and Settings\xxxxxxxxx\Desktop\prime7", line 13, in -toplevel-
    while y < xsqrtr:
KeyboardInterrupt
>>> x
3
>>> y
2
>>> xsqrt
1.7320508075688772
>>> xsqrtr
2.0
>>>

[pointone]

One problem I found is that if you start with 1:

x = begin
import math
while x < max:
    xsqrt = math.sqrt(x)
    xsqrtr = round(xsqrt,0)
    y = 2
    while y < xsqrtr:
        ...

So, x = 1, max = something like 99 or whatever is inputed.

while x < max:

So, 1 is less than 99, it enters a while loop.

    xsqrt = math.sqrt(x)
    xsqrtr = round(xsqrt,0)
    y = 2
    while y < xsqrtr:

It finds the square root, rounds it, then checks to see if 2 is less than 1.0, which it isn't... So it restarts the while loop, because 1 is still less than 99.

You have an infinite loop here.

[Phat Pat]

Originally Posted by pointone

One problem I found is that if you start with 1:

x = begin
import math
while x < max:
    xsqrt = math.sqrt(x)
    xsqrtr = round(xsqrt,0)
    y = 2
    while y < xsqrtr:
        ...

So, x = 1, max = something like 99 or whatever is inputed.

while x < max:

So, 1 is less than 99, it enters a while loop.

    xsqrt = math.sqrt(x)
    xsqrtr = round(xsqrt,0)
    y = 2
    while y < xsqrtr:

It finds the square root, rounds it, then checks to see if 2 is less than 1.0, which it isn't... So it restarts the while loop, because 1 is still less than 99.

You have an infinite loop here.

aha, I'll make some changes and see if that is the last of my problems

thanks!

Edit: just realized I messed up the even/odd test in test1, and the divisibility test in test2. bah

[Phat Pat]

ok, here is something I completely don't understand

while x < max:
    xsqrt = math.sqrt(x)
    xsqrtr = round(xsqrt) + 1
    y = 1
    while y < xsqrtr:
        y = y + 1
        test2 = (x / y) - (x % y)
        if test2 == 0:
            x = x + 2
            break
        if y == xsqrtr:
            print x
            break

still in an endless loop, now printing 7 repeatedly when y = 4 and xsqrtr = 4.0

in the shell, 4 = 4.0

So I'm lost, it should end the second loop, but it doesn't, and even if it doesnt it should keep adding up y, but it doesnt.

[Phat Pat]

hold the phone, might have the solution

edit: yep, fixed it. thanks for the help guys

[pointone]

*EDIT*

Aw, I guess I was too slow! :P



We see it prints "x," so it does break out of the second while loop, and heads back to the first one.

"x" is 7, and I assume it is less than "max," so it enters the first loop again.

xqrt = math.sqrt(x)
xsqrtr = round(xsqrt) + 1

After this bit of code, xsqrtr should equal 4.0 again.

Then we assign "y = 1" and check to see if 1 is less than 4.0, which it is--we enter the second loop.

"y = y + 1," so y = 2.

"test2 = (7 / 2) - (7 % 2)" should evaluate to (3) - (1), or 2, so test2 = 2.

"if 2 == 0:" nope!

"if 2 == 4.0:" nope!

So, restart the loop.

y = 3, test2 will equal 1, nope to both, and restart.

y = 4, test2 will equal -2, nope to "if -2 == 0," but "4 == 4.0" is true, so we print x--which is 7, then break into the first loop.

x is still 7, and I assume it is less than "max..." wait, am I repeating myself?

[Phat Pat]

lol, thanks for the help. Didnt figure it out till I had it print where it was in the code (loop1 and loop2). Now it works like a charm, and I remembered that I had modulus figured out right the first time.

again, thanks for the help!

[Phat Pat]

I, shamefully, have only coded in BASIC before python (class in VisualBasic, then I used Liberty Basic on my own). I wrote the same basic program in Liberty Basic, and it takes almost a minute to calculate the primes up to 100,000. The python script can get to 1,000,000 in the same time. Now I just need to learn C, lol.

[Gizmo]

There are a number of much more efficient ways to calculate the primes between x and y. This is one of the most obvious ways, but is not particularly efficient (as is usually the case).

Glad you figured out your problem. I'm not familiar with Python, so I was thinking I might have to learn a new language before I could help you out. The whole 'indent controls what while clause to use' thing threw me for a minute, 'cause I was looking at the code going "where's the end of the loop?".

[Phat Pat]

Originally Posted by gizmo

There are a number of much more efficient ways to calculate the primes between x and y. This is one of the most obvious ways, but is not particularly efficient (as is usually the case).

Glad you figured out your problem. I'm not familiar with Python, so I was thinking I might have to learn a new language before I could help you out. The whole 'indent controls what while clause to use' thing threw me for a minute, 'cause I was looking at the code going "where's the end of the loop?".

I know there are more efficient ways, but the only one that I can think of (Sieve of Eratosthenes) creates some memory problems at higher numbers. The only other test I've heard of do not have 100% accuracy. I know there are others out there, but I have yet to get a satifactory explanation of them and I dont want to impliment something by copying and pasting a formula if I dont understand how it works (what is the fun in that?).

Yeah, the indents had me doing double takes of everything, especially block If statements (where is the end if? ahhh). Dive into Python was a huge help though.

[danrok]

Just on a side note. Using the word "begin" as a variable name is not such good practice, since that word is often a reserved command in many languages.

[Gizmo]

Originally Posted by Phat Pat

I know there are more efficient ways, but the only one that I can think of (Sieve of Eratosthenes) creates some memory problems at higher numbers.

Sieve is about the best algorithm I know of. To make it scalable to handle more than physical memory will allow, you basically have to implement a paging scheme and use disk storage to hold everything but your current working range. It complicates the algorithm a fair amount, but if you implement it properly, it will let you deal with very, very large primes. Most implementations of the Sieve use a whole char to handle a boolean. With a little creative programming, then, you can implement the memory storage as a linear bit array which increases your capabilities even more. Using a 70GiB drive for storage and implimenting a linear bit array, you can search up to 600 billion numbers.

Going beyond that you could (in principle) run a search over, say, a million numbers in a given range using the Sieve, and then store only the successful results in an array, and page the array out to disk. This would slow the algorithm somewhat, but careful attention to the paging implementation should make it possible to avoid thrashing the disk. Using that implementation then, you could successfully find something upwards of the first four billion primes or so using a 70 GiB disk for storage (assuming 16 bytes of storage for each number). (I have no idea how many actual numbers would be tested to find the first four billion primes, but I suspect it is quite a bit more than the 600 billion numbers we could otherwise represent in that same storage. Primes get rather sparse as the numbers get larger.)

Might be an interesting programming challenge.

[Phat Pat]

Originally Posted by gizmo

Might be an interesting programming challenge.

I think perhaps a bit above my level at the current time, lol. I really have no need for the primes, I'm just messing around with basic optimizations (the BASIC to python move was a huge one, lol).

I'm still waiting for a legitamate need to program for. The biggest thing I have done so far is a Liberty BASIC music conversion program that converts notes between keys (ie on the staff C in Eb to on the staff G in Bb), it also puts out the major triad and the major scale. It is all based on the Circle of Fifths, and runs about 150 lines (It would be around 200 if I took out the in code dictionaries and put the code from them where they are used) Which is pretty hefty for the language. The program could easily be modified (thanks to the wonders of Modes) to output all kinds of things, like minor triads, minor scales, all the Modes, All kinds of chords, etc etc etc. That is my jewel of programming thus far.

Right now, it's just cool to see numbers fly across the screen.