Programming Forums > Script Programming > Python

Vahagn · Feb 1st, 2006, 3:01 PM

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.

Cerulean · Feb 2nd, 2006, 12:25 PM

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.

Vahagn · Feb 3rd, 2006, 8:16 AM

@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

Arevos · Feb 3rd, 2006, 9:11 AM

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:

(Toggle Plain Text)

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".

Dietrich · Feb 3rd, 2006, 9:12 AM

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!

Vahagn · Feb 4th, 2006, 5:54 AM

@ Arevos and Dietrich,-

that's right, thanx.

Vahagn · Feb 4th, 2006, 6:20 AM

Upon 2nd thought:

Quote:

Originally Posted by Arevos

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.

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

Arevos · Feb 4th, 2006, 8:11 AM

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:

(Toggle Plain Text)

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

(Toggle Plain Text)

>>> prime_gen(10)
3
5
7
9
10
11
13
14
15
16

Vahagn · Feb 6th, 2006, 3:00 PM

Quote:

Originally Posted by Arevos

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).

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:

(Toggle Plain Text)

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:

(Toggle Plain Text)

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)

Feb 1st, 2006, 3:01 PM	#1
Vahagn Newbie Join Date: Feb 2006 Posts: 5 Rep Power: 0	KeyboardInterrupt when calling a function Hi, I am toying with the following program to generate prime numbers: (Toggle Plain Text) 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) 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.

Feb 3rd, 2006, 9:12 AM	#5
Dietrich Professional Programmer Join Date: Feb 2005 Posts: 434 Rep Power: 4	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! __________________ I looked it up on the Intergnats!

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Feb 2nd, 2006, 12:25 PM	#2
Cerulean Professional Programmer Join Date: Apr 2005 Location: London, England Posts: 459 Rep Power: 4	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.

Feb 3rd, 2006, 8:16 AM	#3
Vahagn Newbie Join Date: Feb 2006 Posts: 5 Rep Power: 0	@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

Feb 4th, 2006, 5:54 AM	#6
Vahagn Newbie Join Date: Feb 2006 Posts: 5 Rep Power: 0	@ Arevos and Dietrich,- that's right, thanx.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Script Programming > Python

KeyboardInterrupt when calling a function