Python：跳出多层循环

Question

我有一个用于米勒-拉宾素性测试的伪代码：

function isPrime(n, k=5)
    if n < 2 then return False
    for p in [2,3,5,7,11,13,17,19,23,29]
        if n % p == 0 then return n == p
    s, d = 0, n-1
    while d % 2 == 0
        s, d = s+1, d/2
    for i from 0 to k
        x = powerMod(randint(2, n-1), d, n)
        if x == 1 or x == n-1 then next i
        for r from 1 to s
            x = (x * x) % n
            if x == 1 then return False
            if x == n-1 then next i
        return False
    return True

但是把这个伪代码翻译成Python有点困难，因为在内部的for循环中有一个next i语句，它需要同时跳出两个循环。Python里没有goto这个东西。其他在Stack Overflow上问过这个问题的人被建议使用局部函数配合return，或者用try/except条件，或者再加一个布尔标志，但这些解决方案要么不适用，要么会让这个漂亮的伪代码变得很复杂。

那么，解决这个问题的Python方式是什么呢？

Answer 1

你可以在使用 for: else 的时候，结合使用 break 和 continue。

for i from 0 to k
    x = powerMod(randint(2, n-1), d, n)
    # Use 'continue' to go to next i (skip inner loop).
    if x == 1 or x == n-1 then next i
    for r from 1 to s
        x = (x * x) % n
        if x == 1 then return False
        # Use 'break' to exit this loop and go to next i
        # since this loop is at the end of the i loop.
        if x == n-1 then next i
    else:
        # This is only reached if no `break` occurred
        return False
return True

Answer 2

我觉得用 Python 的方式来处理这个问题应该是用 try/except。虽然为了可读性可能更倾向于用一个方法或者布尔值，但我认为只需要加一行代码就能解决这个问题：

    for i in xrange(k):
        x = powerMod(randint(2, n-1), d, n)
        if x == 1 or x == n-1: continue
        for r in xrange(1,s):
            x = (x * x) % n
            if x == 1: return False
            if x == n-1: break #*
        if x != n-1: #added line
            return False
    return True

在标记为 #* 的那一行出错是有问题的，因为它会返回 false，但如果我们修复了这个问题，就像是“下一个 i”一样简单。

另一个解决方案是 tobias_k 提出的，使用 for/else 结构：

    for i in xrange(k):
        x = powerMod(randint(2, n-1), d, n)
        if x == 1 or x == n-1: continue
        for r in xrange(1,s):
            x = (x * x) % n
            if x == 1: return False
            if x == n-1: break 
        else: #added line
            return False
    return True

return False 这行代码只有在循环结束后才会被调用，如果循环是因为 break 被中断的话，就不会执行这行代码。