Проблема с синтаксисом Python - PullRequest
Новая
       5

Проблема с синтаксисом Python

0 голосов
/ 29 июня 2010

Я только что вернулся в Project Euler и потерял свою учетную запись и решения, поэтому я вернулся к проблеме 7. Однако мой код не работает.Мне кажется довольно элементарным, может ли кто-нибудь помочь мне отладить мой (короткий) скрипт?

Должен найти 10001-й премьер. 

#!/usr/bin/env python
#encoding: utf-8
"""
P7.py

Created by Andrew Levenson on 2010-06-29.
Copyright (c) 2010 __ME__. All rights reserved.
"""

import sys
import os
from math import sqrt

def isPrime(num):
    flag = True
    for x in range(2,int(sqrt(num))):
        if( num % x == 0 ):
            flag = False
    if flag == True:
         return True
    else:
         return False

def main():
    i, n = 1, 3
    p = False
    end = 6
    while end - i >= 0:
        p = isPrime(n)
        if p == True:
            i = i + 1
            print n
        n = n + 1

if __name__ == '__main__':
    main()

Редактировать *: Извините, проблема в том, что каждыйчисло простое.: /

Ответы [ 2 ]

5 голосов
/ 29 июня 2010

Синтаксис в порядке (в Python 2). У семантики есть некоторые осложнения, которых можно избежать, и эта ошибка: 

for x in range(2,int(sqrt(num))):
    if( num % x == 0 ):
        flag = False

range(2, Y) переходит от 2 включенных к Y исключенных - поэтому вы часто не проверяете последний возможный делитель и тем самым считаете «простыми числами» многие числа, которых нет. Как самое простое исправление, попробуйте 1 + int(... в этом range. После чего целесообразно устранить эти возможные осложнения: например, 

if somebool: return True
else: return False

никогда не гарантируется, так как более простой return somebool выполняет ту же работу.

Упрощенная версия всего вашего кода (только с необходимыми оптимизациями, но в остальном точно такой же алгоритм) может быть, например: 

from math import sqrt

def isPrime(num):
    for x in range(3, int(1 + sqrt(num)), 2):
        if num % x == 0: return False
    return True

def main():
    i, n = 0, 3
    end = 6
    while i < end:
        if isPrime(n):
            i += 1
            print n
        n += 2

if __name__ == '__main__':
    main()

«Возвращение, как только вы узнаете ответ», уже объяснено, я добавил еще одну важную оптимизацию (+ = 2 вместо 1 для n, поскольку мы «знаем», что четные числа> 3 не являются простых чисел и настройка range по той же причине).

Можно получить симпатичнее, например .:

def isPrime(num):
    return all(num % x for x n range(3, int(1 + sqrt(num)), 2))

хотя это может показаться «проще», если вы не знакомы со встроенным all, это действительно так, потому что это избавляет вас от необходимости (и читателей кода, которым необходимо следовать) низкоуровневой логики, в пользу соответствующего уровня абстракции для выражения ключевой идеи функции, то есть «num является простым, если все возможные нечетные делители имеют остаток [[non-0]] при попытке деления» (т. е. выражают концепцию напрямую в точной, исполняемой форме). Алгоритм внутри фактически все еще идентичен.

Идем дальше ...: 

import itertools as it

def odd():
    for n in it.count(1):
        yield n + n + 1

def main():
    end = 5        
    for i, n in enumerate(it.ifilter(isPrime, odd())):
        print n
        if i >= end: break

Опять же, это тот же алгоритм, что и раньше, только выраженный на более подходящем уровне абстракции: генерация последовательности нечетных чисел (от 3 и выше), помещенных в собственный генератор odd, и некоторое использование встроенных функций enumerate и itertools, чтобы избежать неуместных (и ненужных) низкоуровневых выражений / рассуждений.

Повторюсь: фундаментальной оптимизации пока не применено - просто подходящая абстракция. Оптимизация неограниченной последовательной генерации простых чисел в Python (например, с помощью открытого сита Эратосфена) подробно обсуждалась в другом месте, например. здесь (не забудьте также проверить комментарии!). Здесь я сосредоточился на том, чтобы показать, как (с такими встроенными модулями, как enumerate, all и any, критически важные itertools, плюс генераторы и выражения генератора) многие проблемы зацикливания могут быть выражены в современном Python на более подходящих уровнях абстракции, чем «вдохновленные Си», которые могут показаться наиболее естественными для большинства программистов, которые привыкли к программированию на Си и т.п. (Возможно, к удивлению ученых, привыкших к «штрафу за абстракцию» в C ++, впервые определенному Степановым, Python обычно имеет вместо этого «премию за абстракцию», особенно если itertools, хорошо известный своей невероятной скоростью, широко и соответствующим образом используется ... но это действительно другая тема; -).

1 голос
/ 29 июня 2010

Разве это не лучше? 

def isPrime(num):
    for x in range(2,int(sqrt(num))):
        if( num % x == 0 ):
            return False
    return True

А это: 

def main():
    i, n = 1, 3
    while i <= 6:
        if isPrime(n):
            i = i + 1
            print n
        n = n + 1

Кроме того, я нигде не вижу 10001 ...

...