Programming Forums - KeyboardInterrupt when calling a function

Programming Forums (http://www.programmingforums.org/forumindex.php)

- Python (http://www.programmingforums.org/forum43.html)

- - KeyboardInterrupt when calling a function (http://www.programmingforums.org/showthread.php?t=8219)

KeyboardInterrupt when calling a function

Hi, I am toying with the following program to generate prime numbers:

import sys

from math import sqrt, floor



def prime_gen(count):



    num = 2

    ct = 0  

    while ct < count:

        for i in range(2, int(floor(sqrt(num)))):

            if num % i == 0:             

                num = num + 1

            elif num % i != 0:

                print num

                ct = ct + 1

                num = num + 1               

         

prime_gen(100) 

#x = int(sys.argv[1])

#prime_gen(x)

When I call prime_gen at the prompt (=execute the program), the prompt freezes and I have to exit it with Ctrl+C. The error message says there is a KeyboardInterrupt and the lines 17 and 9 cause the problem, I however do not understand WHAT the problem is - thanks beforehand for help.

V.

KeyboardInterrupt is an exception raised when you hit Ctrl+C - it's a way that you can make your Python code respond when that's done, e.g for stopping execution of your application gracefully. Your prompt is also not freezing, your script is in the middle of execution.

@Cerulean:

If the code is in the middle of execution, how come it is so slow - I run it and wait idefinitely, while the caret blinks? I have a corresponding piece of C-code and it executes in a blink of an eye.
Regards, Vahagn

Quote:

Originally Posted by Vahagn

If the code is in the middle of execution, how come it is so slow - I run it and wait idefinitely, while the caret blinks?

It's because your program has several logic errors that prevent your program terminating.

The first problem is that "int(floor(sqrt(2)))" is equal to 1, and "range(2, 1)" is equal to the empty list "[]". Thus, the inner parts of your for loop are never executed, so ct is never incremented, so your loop never ends.

The second problem is that you have no 'break' statements, and the logic in your if statements appears to be incorrect. ct is incremented every time it cannot divide one number by another. This is different to finding a prime. For instance, 10 cannot be divided cleanly by 3, so when num is 10 and i is 3, ct would be incremented.

The easiest way to get around this problem is to create a separate function to determine whether something is prime:

def is_prime(num):

    for i in range(2, num):

        if num % i == 0:

            return False

    return True

In the above, the moment num is found to be cleanly divisible by another number, the function exits with "False". If it cannot find any such number, it exits with "True".

Your algorithm isn't correct. Put in a test statement like "print ct" right after the while statement line and you will find out the ct is always zero, so while is an endless loop!

@ Arevos and Dietrich,-

that's right, thanx.

Upon 2nd thought:

Quote:

Originally Posted by Arevos

That's the mistake :-) :banana:

Quote:

Originally Posted by Arevos

The second problem is that you have no 'break' statements, and the logic in your if statements appears to be incorrect. ct is incremented every time it cannot divide one number by another. This is different to finding a prime. For instance, 10 cannot be divided cleanly by 3, so when num is 10 and i is 3, ct would be incremented.

ct is incremented every time there is no divisor (the variable i) for a number (num) in the range 2 and the square root of that number. (There is no reason to test higher than the square root, as the other divisor will already be tested for). So to take your example, 10 cannot be divided evenly by 3, but before we test 10/3 we will have tested 10/2, and that will have failed, causing num (10) to be incremented to 11. 11 doesn't have divisors in the range 2, sqrt of 11, so 11 must be a prime, etc.

Cheers,
Vahagn

Quote:

Originally Posted by Vahagn

So to take your example, 10 cannot be divided evenly by 3, but before we test 10/3 we will have tested 10/2, and that will have failed, causing num (10) to be incremented to 11. 11 doesn't have divisors in the range 2, sqrt of 11, so 11 must be a prime, etc.

Ah, I see what you're doing! But it still won't work, because unlike a for-loop in C, your for-loop in Python will not be affected by the value of num whilst the loop is in effect.

You need to run the for loop from the beginning for each number. You need to check that x is not divisible by 2, 3, 4 ... sqrt(x). And then you need to check x + 1 in the same way, ensuring that x + 1 is not divisible by 2, 3, 4 ... sqrt(x + 1).

Your function doesn't do this, because it doesn't reset the for-loop when it finds that a number can be divided cleanly by another.

Let's take num = 21. Your range function will create the list [2, 3, 4], so for the first iteraton, i = 2. The expression (21 % 2 == 0) is false, so 21 will be printed, and num will be incremented to 22. On the next iteration of the loop, i = 3, which again will result in 22 being printed and num will be incremented to 23. On the final iteration of the loop, i = 4, which will result in 23 being printed and num being incremented to 24.

ct still hasn't reached 100, so we go through the for loop again, with [2, 3, 4]. This will result in 25 being printed.

Next iteration, 27, 28, 29 will be printed.

Obviously, these aren't quite primes :)

If I execute it from the beginning, where num = 2 (and a 'max' function to make sure the range is never less than [2]), things don't fair so well, either:

def prime_gen(count):

    num = 2

    ct = 0  

    while ct < count:

        for i in range(2, max(int(floor(sqrt(num))) + 1, 3)):

            if num % i == 0:             

                num = num + 1

            elif num % i != 0:

                print num

                ct = ct + 1

                num = num + 1

>>> prime_gen(10)

3

5

7

9

10

11

13

14

15

16

Quote:

Originally Posted by Arevos

I see what you mean - however expressing that in Python is a different story. Difficult to slip the habit of C and C-derived control structures! When tested separately, your program works fine:

def is_prime(num):

    for i in range(2, num):

        if num % i == 0:

            print num, "is NOT a prime"

            return False

    print num, "is a prime"        

    return True



is_prime(111)

If embedded in another function however, things go haywire:

from math import sqrt, floor

    

def generate(count):    

    

    num = 3 # num = 2 doesn't work - empty list

    ct = 0    



    def is_prime(num):       

        for i in range(2, num):           

            if num % i == 0:               

                print num, "is NOT a prime"

                return False            

            print num, "is a prime"        

            return True

    

    while ct < count:

        if is_prime(num) == True:            

            num = num + 1

            ct = ct + 1        

        elif is_prime(num) == False:

           num = num + 1

            



generate(100)

:rolleyes: