Python语法问题

Question

我刚刚回到Project Euler并且丢失了我的帐户和解决方案,所以我回到了问题7.但是,我的代码不起作用.对我来说这似乎相当原始,有人可以帮助我调试我的(短)脚本吗？

应该找到10001 Prime.

#!/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()

编辑*:对不起,问题在于它说每个数字都是素数.:/

Answer 1

语法很好(在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内置内容,这可能看起来不那么"简单" ,但实际上是这样,因为它可以节省你必须做的事情(代码的读者必须遵循)低级别逻辑,有利于适当的级别用于表达函数关键思想的抽象,即"当尝试除法时所有可能的奇数除数具有[[非0]]余数时,"num是素数"(即,以精确的,可执行的形式直接表达概念) .内部算法实际上仍然相同.

更进一步......:

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中无限连续质数生成的优化(例如通过开放式Eratosthenes Sieve方法)已在其他地方进行了深入讨论,例如此处(请务必查看注释!).在这里,我重点说明如何(内置插件,例如enumerate,all和any,关键itertools,加上生成器和生成器表达式)许多"循环"问题可以在现代Python中以更合适的抽象级别表达,而不是"C级",对于大多数编程人员来说,这些问题对于C编程等都是最自然的.(对于习惯于Stepanov首先确定的C++的"抽象惩罚"的学者来说,可能令人惊讶的是,Python通常倾向于具有"抽象溢价",特别是如果itertools以其超快的速度而众所周知的,它被广泛适当地使用......但是,这是真的是一个不同的主题;-).