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

You say you tried debugging it... Can't you find where it's going wrong on your own? (I did, and it's pretty obvious what's going on) — Kena, Sep 02 '10 at 17:16
I have no clue why I didn't see it. I just started coding a few days ago. So, that might have something to do with it. — JustA., Sep 02 '10 at 17:22

score 4 · Answer 1 · answered Sep 02 '10 at 17:12

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.

score 4 · Accepted Answer · answered Sep 02 '10 at 17:16

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

Aillyn · Answer 3 · 2010-09-02T17:29:05.947

1

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

edited Sep 02 '10 at 17:29

answered Sep 02 '10 at 17:17

Aillyn

23,354
24
59
84

Yes, I noticed that on running and I corrected it. On the other hand, the function doesn't recognize 2 as a prime if I take it as y>1. So, I have to figure that out. Thanks a lot for the optimization trick. – JustA. Sep 02 '10 at 17:30
@JustA: Hardcode 2 to be prime, and only check for divisibility by 2 and by odd numbers >= 3. – Brian Sep 02 '10 at 17:31
@Brian: I'm feeling like a retard right now. I have lots to learn. – JustA. Sep 02 '10 at 17:50
also keep in mind that if you start at 2 and work your way up, the likelihood of getting a match (for the early-out) is much greater. – dash-tom-bang Sep 02 '10 at 19:28

score 0 · Answer 4 · edited May 23 '17 at 12:30

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

Runtime Crash For A Very Basic Python Program

4 Answers4