解题思路

算法概述

1. 转成字符串处理
   将输入的正整数 $n$ 转为长度为 $L$ 的字符串 s。
2. 贪心+回溯构造
   从最高位到最低位逐位决定数字。对第 i 位，我们在合法范围内（若受上界约束则不超过 s[i]，否则不超过 9；且不小于前一位已定的数字）的候选数字中，从大到小尝试最优选择。
3. 可行性剪枝
   每选一个数字 d 之后，根据当前已选的数字和剩余位置，可算出可能的最小/最大剩余位数和：

题目内容

在一个虚拟货币挖矿系统中，每个矿工拥有一定的算力值$n$(范围在$1$ 到$10^{18}$之间)。系统需要为每个矿工分配一个算力档位，这个档位必须是小于等于矿工当前算力$n$的最大“稳定算力档”，并且这个档位的算力值各个数位之和必须是一个质数(质数又称素数。一个大于$1$的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数)。“稳定算力档”定义为从左到右每一位数字都不小于前一位数字，例如$123、111、399$都是符合要求的稳定算力档，像$121、897$

这种则不符合要求。合理分配算力档位有助于提高挖矿效率和稳定性。

输入描述

给定一个正整数$n(1≤n≤10^{18})$

输出描述

返回小于等于$n$的最大稳定算力档，且该整数的所有数位之和为质数。如果不存在这样的整数，则返回$-1$

样例1

输入

111

输出

111

说明

$111$本身即是"稳定算力档"，从左到右每一位数字都不小于前一位数字，$1+1+1=3$是质数，所以函数返回$111$

样例2

输入

1

输出

-1

说明

小于等于$1$的"稳定算力档"只有$1$,$1$的数位之和为$1$,$1$不是质数(质数定义为大于$1$的自然数中，除了$1$和它自身外，不能被其他自然数整除的数)，所以函数返回$-1$

样例3

输入

123

输出

122

说明

首先小于等于$123$的“稳定算力档"有 $123、122、111$等。$123$ 的数位之和为$1+2+3=6$,不是质数，不符合条件。再继续找是$122$，数位之和为$1+2+2=5$是质数符合"稳定算力档条件。$111$的数位之和$1+1+1=3$也为质数也满足"稳定算力档"的条件，但$111$小于$122$，所以小于等于$n$的最大稳定算力档为$122$，函数返回$122$。