3765. 完全质数

题目描述

给你一个整数 num。

如果一个数 num 的每一个前缀和每一个后缀都是质数，则称该数为 完全质数。

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

注意：

一个数的前缀是由该数的前 k 位数字构成的。
一个数的后缀是由该数的后 k 位数字构成的。
质数是大于 1 且只有两个因子（1 和它本身）的自然数。
个位数只有在它是质数时才被视为完全质数。

示例 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⁹

解法

方法一：数学

我们定义一个函数 \(\text{is\_prime}(x)\) 来判断一个数 \(x\) 是否为质数。具体地，如果 \(x < 2\)，则 \(x\) 不是质数；否则，我们检查从 \(2\) 到 \(\sqrt{x}\) 的所有整数 \(i\)，如果存在某个 \(i\) 能整除 \(x\)，则 \(x\) 不是质数，否则 \(x\) 是质数。

接下来，我们将整数 \(\textit{num}\) 转换为字符串 \(s\)，并依次检查 \(s\) 的每个前缀和后缀所对应的整数是否为质数。对于前缀，我们从左到右构造整数 \(x\)，对于后缀，我们从右到左构造整数 \(x\)。如果在检查过程中发现某个前缀或后缀对应的整数不是质数，则返回 \(\text{false}\)；如果所有前缀和后缀对应的整数都是质数，则返回 \(\text{true}\)。

时间复杂度 \(O(\sqrt{n} \times \log n)\)，空间复杂度 \(O(\log n)\)，其中 \(n\) 是整数 \(\textit{num}\) 的大小。

Python3JavaC++GoTypeScript

class Solution:
    def completePrime(self, num: int) -> bool:
        def is_prime(x: int) -> bool:
            if x < 2:
                return False
            return all(x % i for i in range(2, int(sqrt(x)) + 1))

        s = str(num)
        x = 0
        for c in s:
            x = x * 10 + int(c)
            if not is_prime(x):
                return False
        x, p = 0, 1
        for c in s[::-1]:
            x = p * int(c) + x
            p *= 10
            if not is_prime(x):
                return False
        return True

class Solution {
    public boolean completePrime(int num) {
        char[] s = String.valueOf(num).toCharArray();
        int x = 0;
        for (int i = 0; i < s.length; i++) {
            x = x * 10 + (s[i] - '0');
            if (!isPrime(x)) {
                return false;
            }
        }
        x = 0;
        int p = 1;
        for (int i = s.length - 1; i >= 0; i--) {
            x = p * (s[i] - '0') + x;
            p *= 10;
            if (!isPrime(x)) {
                return false;
            }
        }
        return true;
    }

    private boolean isPrime(int x) {
        if (x < 2) {
            return false;
        }
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    bool completePrime(int num) {
        auto isPrime = [&](int x) {
            if (x < 2) {
                return false;
            }
            for (int i = 2; i * i <= x; ++i) {
                if (x % i == 0) {
                    return false;
                }
            }
            return true;
        };

        string s = to_string(num);

        int x = 0;
        for (char c : s) {
            x = x * 10 + (c - '0');
            if (!isPrime(x)) {
                return false;
            }
        }

        x = 0;
        int p = 1;
        for (int i = (int) s.size() - 1; i >= 0; --i) {
            x = p * (s[i] - '0') + x;
            p *= 10;
            if (!isPrime(x)) {
                return false;
            }
        }

        return true;
    }
};

func completePrime(num int) bool {
    isPrime := func(x int) bool {
        if x < 2 {
            return false
        }
        for i := 2; i*i <= x; i++ {
            if x%i == 0 {
                return false
            }
        }
        return true
    }

    s := strconv.Itoa(num)

    x := 0
    for i := 0; i < len(s); i++ {
        x = x*10 + int(s[i]-'0')
        if !isPrime(x) {
            return false
        }
    }

    x = 0
    p := 1
    for i := len(s) - 1; i >= 0; i-- {
        x = p*int(s[i]-'0') + x
        p *= 10
        if !isPrime(x) {
            return false
        }
    }

    return true
}

function completePrime(num: number): boolean {
    const isPrime = (x: number): boolean => {
        if (x < 2) return false;
        for (let i = 2; i * i <= x; i++) {
            if (x % i === 0) {
                return false;
            }
        }
        return true;
    };

    const s = String(num);

    let x = 0;
    for (let i = 0; i < s.length; i++) {
        x = x * 10 + (s.charCodeAt(i) - 48);
        if (!isPrime(x)) {
            return false;
        }
    }

    x = 0;
    let p = 1;
    for (let i = s.length - 1; i >= 0; i--) {
        x = p * (s.charCodeAt(i) - 48) + x;
        p *= 10;
        if (!isPrime(x)) {
            return false;
        }
    }

    return true;
}

3765. 完全质数

题目描述

解法

方法一：数学

评论