Skip to main content
Talentd

Complete Prime Number - Solution & Explanation

MediumMathEnumerationNumber Theory9 min read
Practice this problem

Problem Statement

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

Approach Overview

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.

Solution

We define a function 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 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 false; if all integers corresponding to prefixes and suffixes are prime, we return 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 num.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix Enumeration with Primality TestO(d * sqrt(n))O(1)General solution for checking whether a number is a complete prime
Enumeration with Early Digit PruningO(d * sqrt(n))O(1)When many prefixes can be rejected quickly using digit rules

Video Solution

3765. Complete Prime Number | Biweekly Contest 171 | Leetcode • Rapid Syntax • 236 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Complete Prime Number easy or hard?
The difficulty is usually classified as Medium because it combines two concepts: efficient prime checking and digit prefix enumeration. The implementation is short, but recognizing that every prefix must also be prime is the key insight.
Complete Prime Number Python/Java solution
In Python or Java, repeatedly check if the current number is prime and then divide it by 10 to remove the last digit. Implement a helper function that tests divisibility from 2 up to sqrt(x). Repeat until the number becomes zero or a non‑prime prefix is found.
How to solve Complete Prime Number in O(n)?
The problem typically does not require scanning up to n. Instead, check each digit prefix of the number directly. Using prefix enumeration and a square‑root primality test results in O(d * sqrt(n)) time, which is efficient for typical integer limits.
What is the best approach for Complete Prime Number?
The most practical approach is prefix enumeration combined with a primality test. Start with the full number, check if it is prime, then repeatedly remove the last digit and check each prefix. If every prefix is prime, the number is a complete prime. This runs in O(d * sqrt(n)) time where d is the number of digits.
Is Complete Prime Number asked at Google/Amazon/Meta?
Prime number variations and prefix‑based number checks appear frequently in coding interviews at companies like Google and Amazon. While the exact problem name may vary, interviewers often test understanding of primality testing, digit manipulation, and mathematical reasoning.
What data structure is used in Complete Prime Number?
No complex data structure is required. The solution relies on mathematical operations such as integer division and a loop for primality testing. The focus is on number theory rather than arrays, stacks, or hash maps.
What is the time complexity of Complete Prime Number?
The standard solution runs in O(d * sqrt(n)) time and O(1) space. A number with d digits produces at most d prefixes, and each prefix requires a primality check up to sqrt(value). Since only integer operations are used, the memory overhead stays constant.

Ready to solve this problem?

Practice Complete Prime Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer