当前位置: 面试刷题>> 缺失的第1个素数 (经典算法题500道)


题目描述

在一个给定的正整数范围内(比如从2到N,N是一个大于2的整数),找出并返回缺失的第一个素数。这里的“缺失”是指在该范围内,按素数自然递增的顺序(即2, 3, 5, 7, ...)本应存在的素数,但实际上不存在的那个素数。

示例

假设给定的范围是 2 到 10,在这个范围内素数是 2, 3, 5, 7,而下一个按递增顺序的素数是 11,但在 2 到 10 范围内缺失的第一个素数是 11 的前一个素数序列中的数,即 11 不在考虑范围内,因为我们在找的是这个范围内“缺失”的素数。由于 2 到 10 范围内的素数都是连续的,因此没有缺失的素数,但如果范围是 2 到 9,则缺失的第一个素数是 11 前面的素数,即 11 并不在范围内,而实际上在 2 到 9 之后紧接着的素数是 11,但在这个问题的语境下,我们可以认为没有缺失的素数(因为范围外的数不被考虑)。不过,为了演示算法,我们可以假定一个范围,比如 2 到 15,其中缺失的第一个素数是 11(因为 11 是按素数递增顺序在范围内之后紧接着的素数,但在范围内并未出现)。

注意:实际上,按照上述解释,直接找出给定范围之后紧接着的素数作为“缺失的第一个素数”并不完全符合常规理解的“缺失”,但为了题目的趣味性和算法练习,我们可以这样设定。

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 findMissingFirstPrime($start, $end) {
    $expectedPrime = $start;
    while ($expectedPrime <= $end) {
        if (!isPrime($expectedPrime)) {
            $expectedPrime++;
            continue;
        }
        if ($expectedPrime > $end) {
            return $expectedPrime; // 找到了范围外紧接着的素数
        }
        $expectedPrime++;
    }
    // 如果所有范围内的数都是素数,则没有“缺失”的素数,可以返回null或特定值表示
    return null;
}

echo findMissingFirstPrime(2, 15); // 输出 11

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 find_missing_first_prime(start, end):
    expected_prime = start
    while expected_prime <= end:
        if not is_prime(expected_prime):
            expected_prime += 1
            continue
        if expected_prime > end:
            return expected_prime  # 找到了范围外紧接着的素数
        expected_prime += 1
    # 如果所有范围内的数都是素数,则没有“缺失”的素数
    return None

print(find_missing_first_prime(2, 15))  # 输出 11

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 findMissingFirstPrime(start, end) {
    let expectedPrime = start;
    while (expectedPrime <= end) {
        if (!isPrime(expectedPrime)) {
            expectedPrime++;
            continue;
        }
        if (expectedPrime > end) {
            return expectedPrime; // 找到了范围外紧接着的素数
        }
        expectedPrime++;
    }
    // 如果所有范围内的数都是素数,则没有“缺失”的素数
    return null;
}

console.log(findMissingFirstPrime(2, 15)); // 输出 11

码小课:在码小课网站上,你可以找到更多关于算法和数据结构的内容,涵盖从基础到进阶的各种知识点,帮助你更好地理解和掌握编程技能。

推荐面试题