题目描述补充

题目：判断一个正整数是否可以写成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 示例代码

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 示例代码

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 示例代码

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

码小课网站中有更多相关内容分享给大家学习，包括算法优化、数据结构、面试技巧等，欢迎访问学习。