Program to find the number of integers with exactly 9 divisors

Introduction

In this article, we will discuss how to efficiently count the number of integers up to N that have exactly 9 divisors. This is a commonly asked problem in coding interviews and competitive programming.

Understanding the Problem Statement

Given an integer N, we need to find how many numbers in the range [1, N] have exactly 9 divisors.

Example

Input:

N = 100

Output:

2

Explanation:

The numbers 36 and 100 have exactly 9 divisors:

• Divisors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36 (9 divisors)
• Divisors of 100: 1, 2, 4, 5, 10, 20, 25, 50, 100 (9 divisors)

Thus, the answer is 2.

Mathematical Approach

A number X has exactly 9 divisors if and only if it is of one of the following two forms:

1. Square of a prime number raised to the power of 8
   • Example: p8(where p is a prime number)
   • Example: 28=256 (divisors = 9: 1, 2, 4, 8, 16, 32, 64, 128, 256)
2. Product of two distinct prime numbers, both squared
   • Example: p12×p22​ (where p1 and p2 are prime numbers)
   • Example: 22×32=36 (divisors = 9: 1, 2, 3, 4, 6, 9, 12, 18, 36)

Why This Works?

• If a number X has exactly 9 divisors, then its total number of divisors must be 9.
• The formula for the number of divisors of a number N (based on prime factorization) is: (e1+1)×(e2+1)×⋯×(ek+1)(e1 + 1) \times (e2 + 1) \times \dots \times (ek + 1)(e1+1)×(e2+1)×⋯×(ek+1) where e1, e2, …, ek are the powers of the prime factors.
• The only ways to get 9 divisors from this formula are:
  • 8+1=9 (i.e., p^8)
  • 2+1×2+1=3×3=9 (i.e., p1² × p2²)

Efficient Implementation

To efficiently compute the numbers satisfying the above conditions, we:

1. Generate prime numbers using the Sieve of Eratosthenes (for efficiency).
2. Check for numbers in the given range that fit one of the two patterns.

C++ Implementation

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

// Function to generate prime numbers using Sieve of Eratosthenes
vector<int> generatePrimes(int n) {
    vector<bool> isPrime(n + 1, true);
    vector<int> primes;
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i)
                isPrime[j] = false;
        }
    }

    for (int i = 2; i <= n; i++) {
        if (isPrime[i])
            primes.push_back(i);
    }
    return primes;
}

// Function to count numbers with exactly 9 divisors
int countNumbersWith9Divisors(int N) {
    vector<int> primes = generatePrimes(sqrt(N));
    int count = 0;

    // Case 1: p^8
    for (int prime : primes) {
        long long power8 = pow(prime, 8);
        if (power8 > N) break;
        count++;
    }

    // Case 2: p1^2 * p2^2
    int len = primes.size();
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            long long num = (long long)primes[i] * primes[i] * primes[j] * primes[j];
            if (num > N) break;
            count++;
        }
    }
    return count;
}

int main() {
    int N;
    cout << "Enter N: ";
    cin >> N;
    cout << "Numbers with exactly 9 divisors: " << countNumbersWith9Divisors(N) << endl;
    return 0;
}

Time Complexity

• Sieve of Eratosthenes: O(Nlog⁡log⁡N)O(N \log \log N)O(NloglogN)
• Checking p^8 and p1² × p2²: O(N)O(\sqrt{N})O(N​)
• Overall Complexity: O(N)O(\sqrt{N})O(N​)

Java Implementation

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

public class NineDivisors {
    
    // Function to generate prime numbers using Sieve of Eratosthenes
    static ArrayList<Integer> generatePrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        ArrayList<Integer> primes = new ArrayList<>();
        
        for (int i = 2; i <= n; i++) isPrime[i] = true;

        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i)
                    isPrime[j] = false;
            }
        }

        for (int i = 2; i <= n; i++) {
            if (isPrime[i])
                primes.add(i);
        }
        return primes;
    }

    // Function to count numbers with exactly 9 divisors
    static int countNumbersWith9Divisors(int N) {
        ArrayList<Integer> primes = generatePrimes((int) Math.sqrt(N));
        int count = 0;

        // Case 1: p^8
        for (int prime : primes) {
            long power8 = (long) Math.pow(prime, 8);
            if (power8 > N) break;
            count++;
        }

        // Case 2: p1^2 * p2^2
        int len = primes.size();
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                long num = (long) primes.get(i) * primes.get(i) * primes.get(j) * primes.get(j);
                if (num > N) break;
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter N: ");
        int N = scanner.nextInt();
        scanner.close();

        System.out.println("Numbers with exactly 9 divisors: " + countNumbersWith9Divisors(N));
    }
}

Conclusion

• We efficiently computed numbers with exactly 9 divisors using prime factorization patterns.
• Implemented optimized Sieve of Eratosthenes to generate primes efficiently.
• Time complexity is O(√N), making it suitable for large values of N.

This problem is a great way to learn number theory, prime factorization, and the Sieve of Eratosthenes. Let me know if you