Complete Prime Number - Video Solutions

Problem Overview: A number is called a Complete Prime Number if the number itself is prime and every prefix formed by removing digits from the right is also prime. For example, if n = 233, then 233, 23, and 2 must all be prime. The task is to verify whether a given integer satisfies this property.

Approach 1: Prefix Enumeration with Primality Test (O(d * sqrt(n)) time, O(1) space)

Use a mathematical primality test while iteratively removing digits from the number. Start with the full number n. Check if it is prime using a standard sqrt(n) divisor test. If it is prime, remove the last digit using integer division (n //= 10) and repeat the process for the prefix. Continue until the value becomes zero. If any prefix is not prime, the number fails the condition. This approach works because a number with d digits generates at most d prefixes, and each prefix check uses a standard prime test.

The key insight is that you do not need to generate all substrings or convert digits repeatedly. Integer division naturally produces each prefix. The primality check only needs to test divisors up to sqrt(x), which keeps the check efficient even for larger inputs.

This method relies purely on Math and basic Number Theory. Enumeration is limited to digit prefixes rather than scanning a large numeric range, which keeps the runtime predictable.

Approach 2: Optimized Primality with Early Elimination (O(d * sqrt(n)) time, O(1) space)

You can reduce unnecessary checks by eliminating obvious non‑prime prefixes early. If any prefix ends with an even digit or 5 (except the single-digit primes), it cannot be prime. Perform this quick digit check before running the full divisor loop. Then apply the same prefix iteration using integer division. While the asymptotic complexity remains O(d * sqrt(n)), in practice it skips many expensive primality checks.

This variant still uses the same core idea: iterate through prefixes and verify primality. The difference is practical optimization based on number properties. The solution still relies on mathematical reasoning rather than complex data structures.

Recommended for interviews: The prefix enumeration with a standard primality test is the expected approach. It clearly demonstrates understanding of digit manipulation, divisor-based prime checking, and efficient enumeration. Mentioning quick digit-based pruning is a good follow-up optimization, but the main goal is showing a clean prefix iteration with correct time complexity.