2026-04-16：完全质数。用go语言，给定一个整数 num。判断它是否满足“完全质数”的条件。

如果 num 的任意长度的前缀（取从最高位开始的前 k 位，k=1 到位数）和任意长度的后缀（取从最低位开始的后 k 位，k=1 到位数）所组成的每一个整数，都必须是质数，则称 num 为“完全质数”。

质数指大于 1 且只有两个正因数（1 和它本身）。另外：只有当个位数字本身是质数时，个位对应的前缀/后缀才算满足条件。

若 num 是完全质数返回 true，否则返回 false。

1 <= num <= 1000000000。

输入：num = 23。

输出：true。

解释：

num = 23 的前缀是 2 和 23，它们都是质数。

num = 23 的后缀是 3 和 23，它们都是质数。

所有的前缀和后缀都是质数，所以 23 是完全质数，答案是 true。

题目来自力扣3765。

完全质数判断过程详细步骤（以输入 num=23 为例）

一、整体执行大体流程

整个程序分为主流程和核心判断函数两部分，步骤如下：

1. 主函数接收输入的整数（23），调用完全质数判断函数。
2. 判断函数先把整数转换成字符串，方便逐位截取前缀和后缀。
3. 遍历数字的每一位位置，依次截取所有长度的前缀和所有长度的后缀。
4. 对每一个截取出来的数字，判断是否为质数。
5. 只要有一个前缀/后缀不是质数，直接判定不是完全质数；全部通过则判定是完全质数。
6. 主函数接收判断结果并输出。

二、分步骤详细执行过程（以 num=23 为例）

步骤1：主函数初始化与调用

• 定义输入数字 num = 23。
• 调用 completePrime(23) 函数，开始完全质数判断。

步骤2：数字转字符串（方便截取前缀/后缀）

• 把整数 23 转换成字符串类型 "23"，字符串长度为 2。
• 目的：通过字符串切片，快速截取任意长度的前缀和后缀。

步骤3：遍历每一位位置，逐次校验前缀和后缀

字符串 "23" 有2个字符，对应遍历 2次（索引 0 和 索引 1）：

第一次遍历（索引 i=0）

1. 截取并校验前缀
   • 截取规则：前 i+1 位 → 前1位，得到子串 "2"。
   • 把子串转回整数 2。
   • 判断 2 是否为质数：是质数，校验通过。
2. 截取并校验后缀
   • 截取规则：从索引 i 开始到末尾 → 从0位开始，得到子串 "23"。
   • 把子串转回整数 23。
   • 判断 23 是否为质数：是质数，校验通过。

第二次遍历（索引 i=1）

1. 截取并校验前缀
   • 截取规则：前 i+1 位 → 前2位，得到子串 "23"。
   • 转回整数 23，判断是质数，校验通过。
2. 截取并校验后缀
   • 截取规则：从索引 i 开始到末尾 → 从1位开始，得到子串 "3"。
   • 转回整数 3，判断是质数，校验通过。

步骤4：最终判定

所有前缀（2、23）和所有后缀（3、23）全部都是质数，函数返回 true。

步骤5：主函数输出结果

打印结果 true，程序结束。

三、补充：失败场景示例（辅助理解）

如果输入 num=24：

1. 前缀：2（质数）、24（合数）→ 24 不是质数，直接判定为 false。
2. 后缀：4（合数）、24（合数）→ 同样不满足。

时间复杂度与额外空间复杂度分析

1. 总时间复杂度

设数字的位数为 n（num最大10亿，n最多10位）：

1. 遍历位数：循环执行 n 次。
2. 每次循环：截取2次字符串 + 2次质数判断。
3. 质数判断：使用大数质数检测算法，针对10亿以内的数，判断时间是常数级。

总时间复杂度：O(n)（线性时间复杂度）。
原因：核心耗时只和数字的位数n成正比，n最大为10，执行效率极高。

2. 总额外空间复杂度

程序运行中，额外开辟的内存空间：

1. 存储数字的字符串：占用 n 字节。
2. 存储截取的前缀/后缀子串：每个子串最长n，总占用常数级空间。
3. 大数对象、临时变量：均为常数级空间。

总额外空间复杂度：O(n)（线性空间复杂度）。
原因：额外空间仅和数字的位数n成正比，无大型数据结构，内存占用极小。

总结

1. 执行过程：转字符串→遍历每一位→逐次校验所有前缀/后缀是否为质数→输出结果。
2. 时间复杂度：O(n)（n为数字位数）。
3. 额外空间复杂度：O(n)（n为数字位数）。

Go完整代码如下：

package main

import (
	"fmt"
	"math/big"
	"strconv"
)

func completePrime(num int) bool {
	s := strconv.Itoa(num)
	for i := range len(s) {
		// 前缀
		x, _ := big.NewInt(0).SetString(s[:i+1], 10)
		if !x.ProbablyPrime(0) {
			return false
		}

		// 后缀
		x, _ = big.NewInt(0).SetString(s[i:], 10)
		if !x.ProbablyPrime(0) {
			return false
		}
	}
	return true
}

func main() {
	num := 23
	result := completePrime(num)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import math

def is_prime(n: int) -> bool:
    """判断一个整数是否为素数"""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    # 使用Miller-Rabin素性测试，这里使用确定性版本处理小数字
    # 对于int范围内的数字，测试这些基数就足够了
    if n < 2:
        return False
    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    if n in small_primes:
        return True
    
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    
    def check_composite(a):
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            return False
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                return False
        return True
    
    # 对于小于2^64的数字，这些基数足够
    test_bases = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
    for a in test_bases:
        if a % n == 0:
            continue
        if check_composite(a):
            return False
    return True

def complete_prime(num: int) -> bool:
    """
    检查一个数字是否为"完全素数"：
    数字的所有前缀和后缀都必须是素数
    """
    s = str(num)
    length = len(s)
    
    for i in range(length):
        # 检查前缀（从开头到当前位置）
        prefix = int(s[:i+1])
        if not is_prime(prefix):
            return False
        
        # 检查后缀（从当前位置到结尾）
        suffix = int(s[i:])
        if not is_prime(suffix):
            return False
    
    return True

def main():
    num = 23
    result = complete_prime(num)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <string>
#include <cmath>

// 简单的试除法素性测试（适用于较小的数字）
bool is_prime_simple(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    int limit = static_cast<int>(std::sqrt(n));
    for (int i = 3; i <= limit; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

bool complete_prime(int num) {
    std::string s = std::to_string(num);
    size_t len = s.length();

    for (size_t i = 0; i < len; i++) {
        // 前缀
        std::string prefix_str = s.substr(0, i + 1);
        int prefix = std::stoi(prefix_str);
        if (!is_prime_simple(prefix)) {
            return false;
        }

        // 后缀
        std::string suffix_str = s.substr(i);
        int suffix = std::stoi(suffix_str);
        if (!is_prime_simple(suffix)) {
            return false;
        }
    }
    return true;
}

int main() {
    int num = 23;
    bool result = complete_prime(num);
    std::cout << std::boolalpha << result << std::endl;
    return 0;
}