Welcome to Subscribe On Youtube

3765. Complete Prime Number

Description

You are given an integer num.

A number num is called a Complete Prime Number if every prefix and every suffix of num is prime.

Return true if num is a Complete Prime Number, otherwise return false.

Note:

  • A prefix of a number is formed by the first k digits of the number.
  • A suffix of a number is formed by the last k digits of the number.
  • Single-digit numbers are considered Complete Prime Numbers only if they are prime.

 

Example 1:

Input: num = 23

Output: true

Explanation:

  • ​​​​​​​Prefixes of num = 23 are 2 and 23, both are prime.
  • Suffixes of num = 23 are 3 and 23, both are prime.
  • All prefixes and suffixes are prime, so 23 is a Complete Prime Number and the answer is true.

Example 2:

Input: num = 39

Output: false

Explanation:

  • Prefixes of num = 39 are 3 and 39. 3 is prime, but 39 is not prime.
  • Suffixes of num = 39 are 9 and 39. Both 9 and 39 are not prime.
  • At least one prefix or suffix is not prime, so 39 is not a Complete Prime Number and the answer is false.

Example 3:

Input: num = 7

Output: true

Explanation:

  • 7 is prime, so all its prefixes and suffixes are prime and the answer is true.

 

Constraints:

  • 1 <= num <= 109

Solutions

Solution 1: Mathematics

We define a function $\text{is_prime}(x)$ to determine whether a number $x$ is prime. Specifically, if $x < 2$, then $x$ is not prime; otherwise, we check all integers $i$ from $2$ to $\sqrt{x}$. If there exists some $i$ that divides $x$, then $x$ is not prime; otherwise, $x$ is prime.

Next, we convert the integer $\textit{num}$ to a string $s$, and sequentially check whether the integer corresponding to each prefix and suffix of $s$ is prime. For prefixes, we construct the integer $x$ from left to right; for suffixes, we construct the integer $x$ from right to left. If during the checking process we find that the integer corresponding to some prefix or suffix is not prime, we return $\text{false}$; if all integers corresponding to prefixes and suffixes are prime, we return $\text{true}$.

The time complexity is $O(\sqrt{n} \times \log n)$, and the space complexity is $O(\log n)$, where $n$ is the value of the integer $\textit{num}$.

  • 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;
    }
};


  • 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


  • 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;
}

All Problems

All Solutions