0

SPOJ Prime Generator Python コードで実行時エラー NZEC が発生します。なぜですか?

testcases = raw_input(" ")

def isPrime(n):
    result = True
    if n != 0 and n != 1 and n % 2 != 0 and n % 5 != 0 and n % 7 != 0 and n % 9 != 0:
        if n > 9:
            for i in range(11,n):
                if isPrime(i):
                    if n % i == 0:
                        result = False
            return result
        else:
            return result
    else:
        return False

for count in range(0,testcases):
    m,n = raw_input(" ").split()
    m = int(m)
    n = int(n)
    for i in range(m,n+1):
        if isPrime(i):
            print i
4

2 に答える 2

2

入力に余分な空白があるため、NZEC を取得しています。このようなケースを処理するコードを設計することは難しくありません。入力をすぐに取得し、空白でトークン化します。私がそれをどのように行ったかを見てください。

def isPrime(n):
    result = True
    if n != 0 and n != 1 and n % 2 != 0 and n % 5 != 0 and n % 7 != 0 and n % 9 != 0:
        if n > 9:
            for i in range(11,n):
                if isPrime(i):
                    if n % i == 0:
                        result = False
            return result
        else:
            return result
    else:
        return False

def main():    # Don't leave the code in the global namespace, it runs slower
    import sys
    tokenizedInput = map(int, sys.stdin.read().split())    # Read at once, tokenize
    testcases = tokenizedInput[0]
    readAt = 1    # Position to begin reading
    for count in range(0,testcases):
        m,n = tokenizedInput[readAt:readAt+2]    # Read the tokenized input
        for i in range(m,n+1):
            if isPrime(i):
                print i
        print    # You need to separate two outputs by a line
        readAt = readAt + 2

main()

これで NZEC を取り除くことができます。ただし、あなたのアルゴリズムは非効率的で正しくありません。のサンプル入力テストケースの場合

2
1 10
3 5

変更したコードが出力されるようになりました

3

3

期待される出力

2
3
5
7

3
5
于 2013-01-07T02:49:33.070 に答える
0

>= 11再帰的に呼び出すすべての番号に対してisPrime。数が十分に大きい場合、スタック オーバーフロー エラーが発生します。

SPOJ の Prime Generator 問題には大きな数の制限があります。のように大きな数でプログラムを実行してみてください999900000 1000000000。

于 2012-05-04T04:12:03.543 に答える