Prime numbers have fascinated mathematicians for centuries. Among the many special categories of primes, Chen Primes occupy an interesting place because they extend the idea of twin primes and connect prime numbers with semiprimes.

In this article, we’ll understand:

• What Chen Primes are
• How to identify them efficiently
• How to use the Sieve of Eratosthenes and Smallest Prime Factor (SPF) arrays
• An optimized Python implementation
• Time complexity analysis

What is a Chen Prime?

A prime number P is called a Chen Prime if:

1. P + 2 is also prime, or
2. P + 2 is semiprime

A semiprime is a number that can be expressed as the product of exactly two prime numbers.

Examples:

4 = 2 × 2
6 = 2 × 3
9 = 3 × 3
15 = 3 × 5

All of the above are semiprimes.

Examples of Chen Primes

Let’s examine a few values.

P = 2

P + 2 = 4
4 = 2 × 2

Since 4 is semiprime, 2 is a Chen Prime.

P = 3

P + 2 = 5

5 is prime.

Therefore, 3 is a Chen Prime.

P = 5

P + 2 = 7

7 is prime.

Therefore, 5 is a Chen Prime.

P = 7

P + 2 = 9
9 = 3 × 3

9 is semiprime.

Therefore, 7 is a Chen Prime.

Problem Statement

Given a range:

L, R

Count how many Chen Primes exist within that range.

Example:

L = 2
R = 10

Chen Primes are:

2
3
5
7

Answer:

4

Naive Approach

For every number in the range:

1. Check if it is prime.
2. Compute P + 2.
3. Check whether P + 2 is prime or semiprime.

The problem?

Prime checking for every number individually becomes expensive for large ranges.

For example:

Range size = 10^6

Performing repeated primality tests would be inefficient.

We need something faster.

Efficient Approach

The optimal solution uses:

1. Sieve of Eratosthenes
2. Smallest Prime Factor (SPF)

Step 1: Generate All Primes Using Sieve

The Sieve of Eratosthenes precomputes primality information for all numbers up to:

max(R + 2)

Instead of checking primality repeatedly, we can answer:

is_prime[x]

in constant time.

Step 2: Store Smallest Prime Factors (SPF)

For every number, store its smallest prime divisor.

Example:

This helps us quickly determine whether a number is semiprime.

How to Check a Semiprime

Suppose:

x = 15

Using SPF:

SPF[15] = 3

Then:

q = 15 / 3 = 5

Now verify:

3 is prime
5 is prime

Since:

15 = 3 × 5

15 is semiprime.

The same logic works for:

4 = 2 × 2
9 = 3 × 3
25 = 5 × 5

as well.

Algorithm

For every number P in the range:

Step 1

Check:

is_prime[P]

If false:

Skip

Step 2

Compute:

x = P + 2

Step 3

Check:

is_prime[x]

If true:

Count it

Step 4

Otherwise check:

is_semiprime(x)

If true:

Count it

Optimized Python Implementation

import sys
input = sys.stdin.readline

MAX = 10**6 + 5

# Prime array and SPF array
is_prime = [True] * MAX
spf = list(range(MAX))

is_prime[0] = is_prime[1] = False

for i in range(2, int(MAX**0.5) + 1):
    if is_prime[i]:
        for j in range(i * i, MAX, i):
            is_prime[j] = False

            if spf[j] == j:
                spf[j] = i

def is_semiprime(x):
    p = spf[x]
    q = x // p

    return (
        p * q == x and
        is_prime[p] and
        is_prime[q]
    )

T = int(input())

for _ in range(T):
    L, R = map(int, input().split())

    count = 0

    for p in range(L, R + 1):

        if is_prime[p]:

            x = p + 2

            if is_prime[x] or is_semiprime(x):
                count += 1

    print(count)

Dry Run Example

Input:

L = 2
R = 10

Processing:

P = 2

2 is prime
4 = 2 × 2

Chen Prime ✔

P = 3

5 is prime

Chen Prime ✔

P = 5

7 is prime

Chen Prime ✔

P = 7

9 = 3 × 3

Chen Prime ✔

P = 11

Outside range.

Final count:

4

Complexity Analysis

Sieve Construction

O(N log log N)

This is performed only once.

Semiprime Check

Using SPF:

O(1)

Query Processing

For a range:

[L, R]

Complexity:

O(R − L + 1)

Total Complexity

Preprocessing:
O(N log log N)
Per Query:
O(R − L)

This is highly efficient for competitive programming constraints.

Can We Optimize Further?

For extremely large constraints such as:

10^7
10^8

we can improve performance using:

Prefix Sum Array

Precompute:

chen[i]

where:

chen[i] = Number of Chen Primes ≤ i

Then each query becomes:

answer = chen[R] - chen[L-1]

Query complexity:

O(1)

after preprocessing.

Key Takeaways

• A Chen Prime is a prime number P such that P + 2 is either prime or semiprime.
• The Sieve of Eratosthenes enables constant-time primality checks.
• Smallest Prime Factor (SPF) allows efficient semiprime detection.
• Preprocessing significantly reduces repeated computation.
• For multiple queries, a prefix-sum approach can reduce query time to O(1).

This problem is an excellent example of combining number theory with preprocessing techniques to achieve efficient solutions suitable for competitive programming and coding interviews.