Medium
题目描述
给你一个整数 num。
如果一个数字 num 的每个前缀和每个后缀都是质数，则称该数字为完全质数。
如果 num 是完全质数则返回 true，否则返回 false。
注意：
- 数字的前缀是由该数字的前 k 位数字组成的数字。
- 数字的后缀是由该数字的后 k 位数字组成的数字。
- 单位数字只有在它们是质数的情况下才被认为是完全质数。
示例 1：
输入：num = 23
输出：true
解释：
num = 23 的前缀是 2 和 23，都是质数。
num = 23 的后缀是 3 和 23，都是质数。
所有前缀和后缀都是质数，所以 23 是完全质数，答案是 true。
示例 2：
输入：num = 39
输出：false
解释：
num = 39 的前缀是 3 和 39。3 是质数，但 39 不是质数。
num = 39 的后缀是 9 和 39。9 和 39 都不是质数。
至少有一个前缀或后缀不是质数，所以 39 不是完全质数，答案是 false。
示例 3：
输入：num = 7
输出：true
解释：
7 是质数，所以它的所有前缀和后缀都是质数，答案是 true。
约束条件：
1 <= num <= 10^9
解题思路
解题思路
这道题需要检查一个数字的所有前缀和后缀是否都是质数。我们可以分别生成所有的前缀和后缀，然后逐一检查它们是否为质数。
核心步骤：
- 质数判断函数：实现一个高效的质数判断函数，时间复杂度为 O(√n)
- 生成前缀：通过字符串操作或数学运算生成所有前缀
- 生成后缀：通过字符串操作或数学运算生成所有后缀
- 逐一检查：对每个前缀和后缀进行质数判断
实现方法：
方法一是使用字符串操作，将数字转换为字符串，然后截取前缀和后缀。这种方法直观易懂，代码简洁。
方法二是使用纯数学运算，通过除法和取模运算来生成前缀和后缀。虽然更高效，但代码稍复杂。
注意事项：
- 单位数字的前缀和后缀就是它本身
- 质数判断时要特别处理 1（不是质数）和 2（是质数）
- 对于大数，质数判断的优化很重要
这里采用字符串方法，因为代码更清晰，且在给定约束下性能足够。
代码实现
class Solution {
public:
bool isPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}
bool completePrime(int num) {
string s = to_string(num);
int n = s.length();
// Check all prefixes
for (int i = 1; i <= n; i++) {
int prefix = stoi(s.substr(0, i));
if (!isPrime(prefix)) return false;
}
// Check all suffixes
for (int i = 0; i < n; i++) {
int suffix = stoi(s.substr(i));
if (!isPrime(suffix)) return false;
}
return true;
}
};
class Solution:
def isPrime(self, n: int) -> bool:
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
def completePrime(self, num: int) -> bool:
s = str(num)
n = len(s)
# Check all prefixes
for i in range(1, n + 1):
prefix = int(s[:i])
if not self.isPrime(prefix):
return False
# Check all suffixes
for i in range(n):
suffix = int(s[i:])
if not self.isPrime(suffix):
return False
return True
public class Solution {
private bool IsPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}
public bool CompletePrime(int num) {
string s = num.ToString();
int n = s.Length;
// Check all prefixes
for (int i = 1; i <= n; i++) {
int prefix = int.Parse(s.Substring(0, i));
if (!IsPrime(prefix)) return false;
}
// Check all suffixes
for (int i = 0; i < n; i++) {
int suffix = int.Parse(s.Substring(i));
if (!IsPrime(suffix)) return false;
}
return true;
}
}
var completePrime = function(num) {
function isPrime(n) {
if (n < 2) return false;
if (n === 2) return true;
if (n % 2 === 0) return false;
for (let i = 3; i * i <= n; i += 2) {
if (n % i === 0) return false;
}
return true;
}
const str = num.toString();
const len = str.length;
// Check all prefixes
for (let i = 1; i <= len; i++) {
const prefix = parseInt(str.substring(0, i));
if (!isPrime(prefix)) return false;
}
// Check all suffixes
for (let i = 0; i < len; i++) {
const suffix = parseInt(str.substring(i));
if (!isPrime(suffix)) return false;
}
return true;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(d × √num)，其中 d 是数字的位数，每个前缀/后缀都需要进行质数判断 |
| 空间复杂度 | O(d)，用于存储数字的字符串表示 |