Runtime Crash For A Very Basic Python Program

Question

I work on a windows XP PC with a Python 2.6 install and I was trying to solve a Project Euler problem, but whenever I execute the code the interpreter hangs. I've debugged it through PyScripter, IDLE and MonkeyStudio, but it still doesn't work even for trivial values like 15.

I simply don't understand why. Can you please help me out?

Here's the code:

"""Project Euler Problem 3
Author: A"""

num = 15
prime = [1]
x = long (round(num/2))

def ifprime (x): 
        """ Defining the function that checks if the number is prime or not"""    
        """ Checking if the passed number is prime or not"""

        y = long(round(x/2))
        while y > 0:
                if x%y == 0:
                        return False
                y -= 1
        return True

while x > 0:
    if num%x == 0:
        if ifprime(x):
                print "I've found a prime! "
                print x
                prime[len(prime):] = [x]
        x -= 1

Answer 1

You have an infinite loop:

x -= 1 is never called as it's under the num%x == 0 condition, which never happens (as x never changes its value).

When num is 15, x starts as 7. Then, num % x is 1, therefore the condition is false and x is not decremented - thus looping ad infinitum.

Answer 2

Your x -= 1 statement is indented one level too far.

x will only be decremented when num % x is 0

It should be this:

while x > 0:
    if num%x == 0:
        if ifprime(x):
                print "I've found a prime! "
                print x
                prime[len(prime):] = [x]
    x -= 1

Answer 3

Besides what others have pointed out, your ifprime is wrong. You are checking while y > 0, and of course that tests up to y = 1, and thus will always return false.

And for optimization purposes, you don't have to test up to x/2, you can test up to sqrt(x) and that's good enough.

import math

def ifprime (x): 

    y = math.ceil(math.sqrt(x))

    while y > 1:
        if x % y == 0:
            return False
        y -= 1

    return True

Answer 4

I have dealt so much with primes that I did the complement to find factor and define ifprime using that, for a change.

import math

## I want any which return first not False value
def some(seq):
    for item in seq:
        if item:
            return item

def factor (number):
    """ returns smallest factor of number or None """
    if number < 4: return None
    return some(divisor
                for divisor in [2] + range(3,int(number ** 0.5)+2, 2)
                if not(number % divisor))

# little slower way for fun (because factor gives the factoring it found)
def ifprime(number):
    return number > 1 and not factor(number)

print [number for number in range(100) if ifprime(number)]

(If you need many primes use sieve algorithm instead of prime test.)