Integers with Exactly 9 Divisors in a Range

A positive integer has exactly 9 divisors only if it is a perfect eighth power of a prime or a product of two distinct prime squares.

That single fact reduces the search from scanning every integer up to N to checking a short list of prime-power products. Here is the proof, the algorithm, and the code.

The Divisor-Count Formula

For any positive integer n with prime factorization n = p1^e1 × p2^e2 × … × pk^ek, the total number of positive divisors is given by the divisor function:

d(n) = (e1 + 1) × (e2 + 1) × … × (ek + 1)

The logic: each divisor of n selects, independently for every prime pi, an exponent between 0 and ei. Multiplying the number of choices per prime gives the total divisor count.

Three examples to build intuition before applying this to the 9-divisors problem:

• 12 = 2^2 × 3^1. d(12) = (2+1)(1+1) = 6. Divisors: 1, 2, 3, 4, 6, 12.
• 36 = 2^2 × 3^2. d(36) = (2+1)(2+1) = 9. Divisors: 1, 2, 3, 4, 6, 9, 12, 18, 36.
• 256 = 2^8. d(256) = (8+1) = 9. Divisors: 1, 2, 4, 8, 16, 32, 64, 128, 256.

Both 36 and 256 have exactly 9 divisors and come from structurally different forms. That distinction is what drives the algorithm.

The divisor-count formula also underlies the related perfect number check, where the sum of divisors matters rather than the count.

Two and Only Two Forms with Exactly 9 Divisors

For d(n) = 9, we need the product (e1+1)(e2+1)…(ek+1) = 9. Every factor here must be at least 2, since every exponent ei ≥ 1 for any prime that genuinely appears in n’s factorization. The question reduces to: in how many ways can 9 be written as a product of integers all ≥ 2?

Since 9 is odd, no factor of 2 can appear. Its only divisors greater than 1 are 3 and 9. This yields exactly two factorizations:

• 9 = 9 (one factor): e1 = 8, so n = p^8 for a single prime p.
• 9 = 3 × 3 (two factors): e1 = e2 = 2, so n = p^2 × q^2 for two distinct primes p and q.

A three-prime form would require at least three factors all ≥ 2, with minimum product 2 × 2 × 2 = 8. The only candidate path to 9 using all-odd factors would be 3 × 3 × 1 = 9, but a factor of 1 corresponds to an exponent of 0, meaning that prime is not actually present. So no valid three-prime form exists.

The complete integer sequence produced by these two forms is catalogued in OEIS A030513.

The Algorithm: Sieve and Two Loops

Given N, the goal is to count integers from 1 to N that have exactly 9 divisors. The algorithm has three steps.

Step 1: Generate primes up to sqrt(N)

Run the Sieve of Eratosthenes up to floor(sqrt(N)). This single list of primes is sufficient for both forms:

• For p^8: we need p ≤ N^(1/8). Since N^(1/8) ≤ sqrt(N) for all N ≥ 1, every qualifying prime is in the list.
• For p^2 × q^2: both p and q must satisfy p^2 × q^2 ≤ N, which forces p, q ≤ sqrt(N).

The sieve runs in O(sqrt(N) × log log sqrt(N)) time and uses O(sqrt(N)) memory. For the memory trade-off analysis, see space complexity of algorithms with worked examples.

Step 2: Count p^8 candidates

Loop over every prime p in the list. Add 1 to the count if p^8 ≤ N. Since the primes list is sorted, exit the loop on the first miss.

Step 3: Count p^2 × q^2 candidates

Loop over all ordered pairs (i, j) with i < j, both indices into the primes list. If primes[i]^2 × primes[j]^2 ≤ N, increment the count. When the inner prime causes the product to exceed N, break the inner loop; all subsequent inner primes are larger and will only push the product further past the limit.

Python Implementation

import math

def sieve_of_eratosthenes(limit):
    sieve = [True] * (limit + 1)
    sieve[0] = sieve[1] = False
    for start in range(2, int(math.sqrt(limit)) + 1):
        if sieve[start]:
            for multiple in range(start * start, limit + 1, start):
                sieve[multiple] = False
    return [num for num, is_prime in enumerate(sieve) if is_prime]


def count_integers_with_9_divisors(N):
    if N < 1:
        return 0
    limit = int(math.sqrt(N))
    primes = sieve_of_eratosthenes(limit)
    count = 0

    # Form 1: p^8
    for p in primes:
        if p ** 8 <= N:
            count += 1
        else:
            break  # sorted list, product only grows from here

    # Form 2: p^2 * q^2, where p and q are distinct primes, p < q
    for i in range(len(primes)):
        for j in range(i + 1, len(primes)):
            if primes[i] ** 2 * primes[j] ** 2 <= N:
                count += 1
            else:
                break  # inner prime is larger, product only grows

    return count

The early break in both loops is not just an optimisation: for large N it converts what would otherwise be a full quadratic scan into a tight pass over only the qualifying pairs.

Worked Examples

Example 1: N = 100

Primes up to sqrt(100) = 10: [2, 3, 5, 7].

• Form p^8:
  • 2^8 = 256 > 100. No prime qualifies. Count from this form: 0.
• Form p^2 × q^2:
  • 2^2 × 3^2 = 4 × 9 = 36 ≤ 100. Count.
  • 2^2 × 5^2 = 4 × 25 = 100 ≤ 100. Count.
  • 2^2 × 7^2 = 4 × 49 = 196 > 100. Break inner loop (p = 2).
  • 3^2 × 5^2 = 9 × 25 = 225 > 100. Break inner loop (p = 3).
  • Count from this form: 2.
• Total: 2. The two qualifying numbers are 36 and 100.

Note: the legacy WP article states “only p=2 works” for the p^8 case here, which contradicts the calculation it gives (2^8 = 256 > 100). The correct conclusion is that no prime satisfies p^8 ≤ 100. The algorithm’s output of 2 is correct; all qualifying numbers come from the p^2 × q^2 form.

Example 2: N = 1000

Primes up to sqrt(1000) ≈ 31: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31].

• Form p^8:
  • 2^8 = 256 ≤ 1000. Count.
  • 3^8 = 6561 > 1000. Break.
  • Count from this form: 1.
• Form p^2 × q^2 (p = 2): 36, 100, 196, 484, 676 qualify; 2^2 × 17^2 = 1156 > 1000.
• Form p^2 × q^2 (p = 3): 225, 441 qualify; 3^2 × 11^2 = 1089 > 1000.
• Form p^2 × q^2 (p = 5): 5^2 × 7^2 = 1225 > 1000. No pairs qualify.
• Count from p^2 × q^2 form: 7.
• Total: 8. The eight numbers in sorted order: 36, 100, 196, 225, 256, 441, 484, 676.

Reducing “all integers up to N” down to “a handful of prime-power products” is the same structural move that makes placement coding rounds tractable: identify the mathematical constraint, then code the check. TinkerLLM at ₹299 is where engineering students are currently applying that constraint-first thinking to build tools with actual LLM APIs.

For more number-theory exercises, digit-sum programs in Python cover a similarly compact problem where the right loop structure matters more than brute force.