当前位置： 面试刷题>> 判断是否可以写成k个素数之和 (经典算法题500道)
### 题目描述补充
题目：**判断一个正整数是否可以写成k个素数之和**
给定一个正整数`n`和一个正整数`k`，判断是否存在`k`个不同的素数（质数），它们的和等于`n`。如果存在，则返回`true`；否则，返回`false`。
### 示例
- 输入：`n = 10, k = 3`
- 输出：`true`（因为`2 + 3 + 5 = 10`）
- 输入：`n = 17, k = 2`
- 输出：`false`（因为不存在两个不同素数之和为17）
### 解题思路
1. **生成素数列表**：首先，我们需要一个函数来生成小于等于`n`的所有素数。
2. **回溯搜索**：使用回溯法（或称为深度优先搜索）来尝试所有可能的素数组合，直到找到和为`n`的`k`个素数，或者确定不存在这样的组合。
### PHP 示例代码
```php
function isPrime($num) {
if ($num <= 1) return false;
for ($i = 2; $i * $i <= $num; $i++) {
if ($num % $i == 0) return false;
}
return true;
}
function generatePrimes($n) {
$primes = [];
for ($i = 2; $i <= $n; $i++) {
if (isPrime($i)) {
$primes[] = $i;
}
}
return $primes;
}
function canBeSummedByKPrimes($n, $k, $primes, $current = [], $index = 0, $sum = 0) {
if ($k == 0 && $sum == $n) return true; // 找到解
if ($k == 0 || $index == count($primes)) return false; // 超出范围或k为0但sum不为n
// 不选择当前素数
if (canBeSummedByKPrimes($n, $k, $primes, $current, $index + 1, $sum)) {
return true;
}
// 选择当前素数
if ($k > 0 && $sum + $primes[$index] <= $n) {
$current[] = $primes[$index];
if (canBeSummedByKPrimes($n, $k - 1, $primes, $current, $index + 1, $sum + $primes[$index])) {
return true;
}
// 回溯
array_pop($current);
}
return false;
}
function canBeSummed($n, $k) {
$primes = generatePrimes($n);
return canBeSummedByKPrimes($n, $k, $primes);
}
// 示例
echo canBeSummed(10, 3) ? 'true' : 'false'; // 输出 true
echo canBeSummed(17, 2) ? 'true' : 'false'; // 输出 false
```
### Python 示例代码
```python
def is_prime(num):
if num <= 1:
return False
for i in range(2, int(num**0.5) + 1):
if num % i == 0:
return False
return True
def generate_primes(n):
return [i for i in range(2, n + 1) if is_prime(i)]
def can_be_summed_by_k_primes(n, k, primes, current=None, index=0, sum_so_far=0):
if current is None:
current = []
if k == 0 and sum_so_far == n:
return True
if k == 0 or index == len(primes):
return False
# 不选择当前素数
if can_be_summed_by_k_primes(n, k, primes, current, index + 1, sum_so_far):
return True
# 选择当前素数
if k > 0 and sum_so_far + primes[index] <= n:
current.append(primes[index])
if can_be_summed_by_k_primes(n, k - 1, primes, current, index + 1, sum_so_far + primes[index]):
return True
current.pop()
return False
def can_be_summed(n, k):
primes = generate_primes(n)
return can_be_summed_by_k_primes(n, k, primes)
# 示例
print(can_be_summed(10, 3)) # 输出 True
print(can_be_summed(17, 2)) # 输出 False
```
### JavaScript 示例代码
```javascript
function isPrime(num) {
if (num <= 1) return false;
for (let i = 2; i * i <= num; i++) {
if (num % i === 0) return false;
}
return true;
}
function generatePrimes(n) {
let primes = [];
for (let i = 2; i <= n; i++) {
if (isPrime(i)) {
primes.push(i);
}
}
return primes;
}
function canBeSummedByKPrimes(n, k, primes, current = [], index = 0, sum = 0) {
if (k === 0 && sum === n) return true;
if (k === 0 || index === primes.length) return false;
// 不选择当前素数
if (canBeSummedByKPrimes(n, k, primes, current, index + 1, sum)) {
return true;
}
// 选择当前素数
if (k > 0 && sum + primes[index] <= n) {
current.push(primes[index]);
if (canBeSummedByKPrimes(n, k - 1, primes, current, index + 1, sum + primes[index])) {
return true;
}
current.pop();
}
return false;
}
function canBeSummed(n, k) {
const primes = generatePrimes(n);
return canBeSummedByKPrimes(n, k, primes);
}
// 示例
console.log(canBeSummed(10, 3)); // 输出 true
console.log(canBeSummed(17, 2)); // 输出 false
```
**码小课网站中有更多相关内容分享给大家学习**，包括算法优化、数据结构、面试技巧等，欢迎访问学习。