Сбой во время выполнения для очень простой программы Python

Question

Я работаю на ПК с Windows XP с установкой Python 2.6, и я пытался решить проблему Project Euler, но всякий раз, когда я выполняю код, интерпретатор зависает.Я отлаживал его через PyScripter, IDLE и MonkeyStudio, но он все еще не работает даже для тривиальных значений, таких как 15.

Я просто не понимаю, почему.Можете ли вы помочь мне?

Вот код:

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

Ваш оператор x - = 1 имеет отступ на один уровень слишком далеко.

x будет уменьшаться только тогда, когда num% x равно 0

Это должно быть так:

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 2

У вас есть бесконечный цикл:

x -= 1 никогда не вызывается, поскольку он находится в условии num%x == 0, чего никогда не происходит (так как x никогда не меняет своего значения).

Когда num равно 15, x начинается как 7. Тогда num % x равно 1, следовательно, условие ложно и x не уменьшается, что приводит к циклу до бесконечности.

Answer 3

Кроме того, что указали другие, ваш ifprime неверен.Вы проверяете while y > 0 и, конечно, проверяете до y = 1 и, таким образом, всегда возвращаете false.

И для целей оптимизации вам не нужно проверять до x/2можно проверить до sqrt(x), и этого достаточно.

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

У меня столько раз получалось с простыми числами , что я сделал дополнение, чтобы найти фактор и определить ifprime, используя его для изменения.

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

(Если вам нужно много простых чисел, используйте алгоритм сита вместо простого теста.)