Find Out Prime or Composite

Problem Statement

You are given a list of integers. For each element, determine whether it is a prime number or a composite number. A prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself. A composite number is a positive integer greater than 1 that is not prime.

Write a function that takes the list and returns a list of strings, where each string is "Prime" if the corresponding number is prime, or "Composite" if it is composite.

Function Signature

def classify_primes(nums: List[int]) -> List[str]:
    pass

Input

• nums: a list of integers. The list length N satisfies $1 \le N \le 10^5$.
• Each integer nums[i] satisfies 1 ≤ nums[i] ≤ 10^6.

Output

• Return a list of strings of length N. The i-th string is "Prime" if nums[i] is prime, otherwise "Composite".

Note

• The number 1 is neither prime nor composite; for the purposes of this problem, treat 1 as composite.
• A prime number is a positive integer greater than 1 that has exactly two distinct positive divisors: 1 and itself.

Constraints

• $1 \le N \le 10^5$
• 1 ≤ nums[i] ≤ 10^6

Examples

Example 1

Input: nums = [541, 37, 113, 5, 10]
Output: ["Prime", "Prime", "Prime", "Prime", "Composite"]

Explanation:

• 541, 37, 113, and 5 are all prime numbers.
• 10 is composite (divisible by 2 and 5).

Example 2

Input: nums = [2, 3, 4, 1]
Output: ["Prime", "Prime", "Composite", "Composite"]

Explanation:

• 2 and 3 are primes.
• 4 is composite (2 × 2).
• 1 is treated as composite.