题解 | 星际跃迁的稳定信标

一种按规则枚举的方法，更容易想出来

def is_prime(num):
    if num == 2:
        return True
    if num < 2:
        return False
    for demon in range(2, int(num**0.5)+1):
        if num % demon == 0:
            return False
    return True


def main():
    f_max = map(int, list(input()))
    f = []
    reduced = False
    for i, d in enumerate(f_max):
        if i == 0:
            f.append(d)
        elif reduced:
            f.append(9)
        else:
            f.append(d)
            for j in range(0, i):
                if f[i-j] < f[i-j-1]:
                    f[i-j-1] -= 1
                    f[i-j] = 9
                    reduced = True
    
    l = len(f)
    while f[-1] > 0:
        if is_prime(sum(f)):
            return int("".join(map(str, f)))
        f[-1] -= 1
        for i in range(1, l):
            if f[-i] < f[-i-1]:
                f[-i-1] -= 1
                f[-i] = 9
    
    return -1


out = main()
print(out)