Integers with Exactly 9 Divisors: C++, Java, Python

Given an integer N, count how many numbers in the range 1 to N have exactly 9 divisors. The problem appears in placement coding assessments and competitive programming rounds, and it has a tight closed-form solution that requires generating primes only up to sqrt(N).

The Two Number Forms That Have Exactly 9 Divisors

The number of divisors of a positive integer n with prime factorization n = p1^e1 * p2^e2 * ... * pk^ek equals (e1+1)(e2+1)...(ek+1) (see Wikipedia: Divisor function). For this product to equal 9, there are exactly two factorizations of 9:

• 9 = 9 × 1: a single prime factor with exponent 8, giving the form p^8.
• 9 = 3 × 3: two distinct prime factors each with exponent 2, giving the form p^2 * q^2.

No other exponent combination works. This article focuses on the code. The derivation from first principles is covered in the companion article on the divisor-count formula.

Working through N = 100 by hand confirms both cases:

• p^8 case: 2^8 = 256 > 100, so no numbers of this form are in range.
• p^2 * q^2 case: 2^2 * 3^2 = 36 and 2^2 * 5^2 = 100 both qualify; 2^2 * 7^2 = 196 > 100 stops the search for p = 2. Answer: 2.

Algorithm: Sieve and Two-Case Iteration

The algorithm runs in three steps:

1. Build all primes up to floor(sqrt(N)) using the Sieve of Eratosthenes.
2. Case 1 — p^8: iterate the prime list; for each prime p, compute p^8; stop when p^8 > N; increment count for each qualifying prime.
3. Case 2 — p^2 * q^2: iterate pairs of distinct primes (p, q) with p < q; for each outer prime p, iterate q values until p^2 * q^2 > N; increment count for each qualifying pair.

Why sqrt(N) is the right sieve ceiling: for Case 1, p^8 <= N requires p <= N^(1/8), which is well below sqrt(N). For Case 2, p^2 * q^2 <= N means (p * q)^2 <= N, so p * q <= sqrt(N). Since both p and q are positive primes with p < q, both must be smaller than sqrt(N).

The sieve itself is an O(sqrt(N)) array, comparable in structure to the linear scan in array traversal problems, where a single initialisation pass sets up the working structure for the iteration that follows.

Precision pitfall in C++

std::pow() returns a double. For p = 13, (long long)pow(13.0, 8.0) can return 815730720 instead of 815730721 due to floating-point rounding. The fix is integer multiplication: compute p2 = p * p, then p8 = p2 * p2 * p2 * p2. Python integers are arbitrary precision so the exponentiation operator ** is always exact. Java’s long arithmetic is exact when there is no overflow; for N up to 10^9 the largest relevant p^8 is 13^8 = 815730721, which fits comfortably in a long.

C++ Implementation

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<int> buildSieve(int limit) {
    if (limit < 2) return {};
    vector<bool> isPrime(limit + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; (long long)i * i <= limit; i++) {
        if (isPrime[i])
            for (int j = i * i; j <= limit; j += i)
                isPrime[j] = false;
    }
    vector<int> primes;
    for (int i = 2; i <= limit; i++)
        if (isPrime[i]) primes.push_back(i);
    return primes;
}

int count9Divisors(int N) {
    int limit = (int)sqrt((double)N);
    vector<int> primes = buildSieve(limit);
    int count = 0;

    // Case 1: p^8 — use integer multiplication to avoid pow() rounding
    for (int p : primes) {
        long long p2 = (long long)p * p;
        long long p8 = p2 * p2 * p2 * p2;
        if (p8 > N) break;
        count++;
    }

    // Case 2: p^2 * q^2
    int n = primes.size();
    for (int i = 0; i < n; i++) {
        long long pi2 = (long long)primes[i] * primes[i];
        for (int j = i + 1; j < n; j++) {
            long long pj2 = (long long)primes[j] * primes[j];
            if (pi2 * pj2 > N) break;
            count++;
        }
    }
    return count;
}

int main() {
    int N;
    cin >> N;
    cout << count9Divisors(N) << endl;
    return 0;
}

The break in Case 2 exits only the inner loop. The outer loop continues for the next prime. This is correct: once pi2 * pj2 > N for the smallest remaining q, all larger q values will also exceed N for the same p.

Java and Python Implementations

Java

import java.util.ArrayList;
import java.util.Scanner;

public class NineDivisors {

    static ArrayList<Integer> buildSieve(int limit) {
        if (limit < 2) return new ArrayList<>();
        boolean[] isPrime = new boolean[limit + 1];
        for (int i = 2; i <= limit; i++) isPrime[i] = true;
        for (int i = 2; (long) i * i <= limit; i++) {
            if (isPrime[i])
                for (int j = i * i; j <= limit; j += i)
                    isPrime[j] = false;
        }
        ArrayList<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= limit; i++)
            if (isPrime[i]) primes.add(i);
        return primes;
    }

    static int count9Divisors(int N) {
        int limit = (int) Math.sqrt(N);
        ArrayList<Integer> primes = buildSieve(limit);
        int count = 0;

        // Case 1: p^8
        for (int p : primes) {
            long p2 = (long) p * p;
            long p8 = p2 * p2 * p2 * p2;
            if (p8 > N) break;
            count++;
        }

        // Case 2: p^2 * q^2
        int sz = primes.size();
        for (int i = 0; i < sz; i++) {
            long pi2 = (long) primes.get(i) * primes.get(i);
            for (int j = i + 1; j < sz; j++) {
                long pj2 = (long) primes.get(j) * primes.get(j);
                if (pi2 * pj2 > N) break;
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(count9Divisors(N));
        sc.close();
    }
}

Python

import math

def build_sieve(limit):
    if limit < 2:
        return []
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i <= limit:
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
        i += 1
    return [i for i in range(2, limit + 1) if is_prime[i]]

def count_9_divisors(n):
    limit = math.isqrt(n)
    primes = build_sieve(limit)
    count = 0

    # Case 1: p^8
    for p in primes:
        if p ** 8 > n:
            break
        count += 1

    # Case 2: p^2 * q^2
    for i in range(len(primes)):
        pi2 = primes[i] ** 2
        for j in range(i + 1, len(primes)):
            if pi2 * primes[j] ** 2 > n:
                break
            count += 1

    return count

if __name__ == "__main__":
    n = int(input())
    print(count_9_divisors(n))

Python’s math.isqrt returns an exact integer square root: no floating-point involved at any step.

Complexity, Edge Cases, and Sample I/O

Time complexity: the sieve up to sqrt(N) runs in O(sqrt(N) * log(log(sqrt(N)))). The prime-pair loop is bounded by the number of primes below sqrt(N), which is approximately sqrt(N) / log(sqrt(N)) by the prime number theorem. The overall complexity is O(sqrt(N) * log(log(N))).

Space complexity: O(sqrt(N)) for the boolean sieve array and the prime list. The count variable and loop indices add only constant overhead.

Edge cases to test:

• N = 0 or N = 1: the sieve produces no primes; both loops return 0 immediately. Correct.
• N = 35: the smallest qualifying number is 36, so the answer is 0.
• N = 36: exactly 1 (the number 36 itself, 2^2 * 3^2).
• N = 256: adds 256 (2^8) to the count. For N = 256, answer = 4 (36, 100, 196, 256).
• Large N: verify no integer overflow. The largest p^8 <= 10^9 is 13^8 = 815730721. Using long long in C++ and long in Java handles this without overflow.

Verified sample I/O:

N	Count	Numbers with exactly 9 divisors
100	2	36, 100
500	7	36, 100, 196, 225, 256, 441, 484
1000	8	36, 100, 196, 225, 256, 441, 484, 676

The O(sqrt(N)) sieve and two-case loop structure appear in a range of placement coding problems. For more patterns at this difficulty, commonly asked coding interview problems and similar competitive programming problems cover adjacent techniques worth practising before an assessment.

The two-case approach here, where a single sieve pass up to sqrt(N) feeds two O(sqrt(N)) iteration loops, is exactly the kind of number theory pattern that placement coding rounds use to test mathematical reasoning alongside programming skill. TinkerLLM is the entry point at ₹299 for students who want to build and deploy Python projects that go beyond solved textbook problems.