python - 素数指示器将大量非素数指示为素数

Question

def main():
    try:
        a = int(input())
        if isinstance(a, int):
            a = int(a)
            if a ==2:
                print('YES')
            if a > 1:
                for i in range(2, a):
                    if a % i == 0:
                        print('NO')
                        break
                    else:
                        print('YES')
                        break
            else:
                print('NO')
        else:
            print('NO')
    except EOFError:
        print('NO')
    except ValueError:
        print('NO')
main()

这段代码正在工作，但它正在计算大量数字作为素数，例如 3456734572525。5 个测试用例中有 4 个是成功的。首先我认为它在 0 或十进制数字上失败，但事实并非如此。

标签： pythonnumbers

Answer 1

for 循环永远不会运行到最后，因为无论a % i == 0您是否会中断循环。您应该将您print("YES")的循环移出并使用returnenstead ofbreak来确保您的函数在循环中断时不会运行此代码。试试这个：

def main():
    try:
        a = int(input())
        if isinstance(a, int):
            a = int(a)
            if a ==2:
                print('YES')
            if a > 1:
                for i in range(2, a):
                    if a % i == 0:
                        print('NO')
                        return
                print('YES')
                return
            else:
                print('NO')
        else:
            print('NO')
    except EOFError:
        print('NO')
    except ValueError:
        print('NO')
main()