题解 | 小红的“质数”寻找

package main
/* 
数位和在连续整数中变化缓慢。
连续几十个数的数位和会覆盖一个范围。
质数在小范围内很密集（比如 2 到 100 内有 25 个质数）。
所以，从 x 开始，不用检测x次，在小范围内就已经能大概率找到一个数位和为质数的数。
 */
import (
	"bufio"
	"fmt"
	"os"
)

const MAX_SUM = 1000000 // 最大数位和估计：10万位 * 9 = 900000
var isPrime [MAX_SUM]bool

// 预处理质数表
func sieve() {
	for i := 2; i < MAX_SUM; i++ {
		isPrime[i] = true
	}
	for i := 2; i*i < MAX_SUM; i++ {
		if isPrime[i] {
			for j := i * i; j < MAX_SUM; j += i {
				isPrime[j] = false
			}
		}
	}
}

// 字符串加一，返回新字符串
func addOne(s string) string {
	bytes := []byte(s)
	carry := 1
	for i := len(bytes) - 1; i >= 0 && carry > 0; i-- {
		digit := int(bytes[i]-'0') + carry
		bytes[i] = byte(digit%10 + '0')
		carry = digit / 10
	}
	if carry > 0 {
		bytes = append([]byte{'1'}, bytes...)
	}
	return string(bytes)
}

// 计算字符串表示的数的数位和
func digitSum(s string) int {
	sum := 0
	for i := 0; i < len(s); i++ {
		sum += int(s[i] - '0')
	}
	return sum
}

// 字符串乘以2（返回字符串）
func multiplyByTwo(s string) string {
	bytes := []byte(s)
	carry := 0
	for i := len(bytes) - 1; i >= 0; i-- {
		digit := int(bytes[i] - '0')
		total := digit*2 + carry
		bytes[i] = byte(total%10 + '0')
		carry = total / 10
	}
	if carry > 0 {
		bytes = append([]byte{byte(carry + '0')}, bytes...)
	}
	return string(bytes)
}

// 比较两个数字字符串 a <= b
func lessOrEqual(a, b string) bool {
	if len(a) != len(b) {
		return len(a) < len(b)
	}
	return a <= b // 字典序此时等于数值序
}

func main() {
	sieve()
	var T int
	fmt.Scan(&T)

	reader := bufio.NewReader(os.Stdin)
	for t := 0; t < T; t++ {
		var x string
		fmt.Fscan(reader, &x)

		twoX := multiplyByTwo(x)
		current := x
		found := false
		// 最多尝试 60000 次, 为50000时，有一个样例过不了
		for i := 0; i < 60000 && lessOrEqual(current, twoX); i++ {
			sum := digitSum(current)
			if sum < MAX_SUM && isPrime[sum] {
				fmt.Println(current)
				found = true
				break
			}
			current = addOne(current)
		}
		if !found {
			fmt.Println(-1)
		}
	}
}