Number Of Integers Which Has Exactly 9 Divisors In Java

Introduction

Finding numbers with a specific count of divisors is a classic problem in number theory. In this article, you will learn how to identify integers that have exactly nine divisors using Java.

Problem Statement

The challenge is to determine how many integers, within a given range (e.g., up to a certain limit), possess precisely nine divisors. This requires an understanding of how the number of divisors relates to a number's prime factorization.

Example

Consider the number 36. Its divisors are 1, 2, 3, 4, 6, 9, 12, 18, 36. There are exactly 9 divisors.

Background & Knowledge Prerequisites

To understand the solution, you should be familiar with:

• Prime Factorization: Expressing a number as a product of its prime factors (e.g., 12 = 2^2 \* 3^1).
• Number of Divisors Formula: If a number N has a prime factorization of p1^a1 * p2^a2 * ... * pk^ak, then the total number of divisors D(N) is given by (a1+1) * (a2+1) * ... * (ak+1).
• Basic Java Programming: Loops, conditional statements, and methods.

Use Cases or Case Studies

• Number Theory Research: Investigating properties of integers.
• Competitive Programming: Solving algorithmic challenges that involve divisor counts.
• Cryptography: Understanding properties of numbers can be relevant in certain cryptographic algorithms.
• Educational Tools: Creating programs to demonstrate number theory concepts.

Solution Approaches

To have exactly 9 divisors, a number N must satisfy (a1+1) * (a2+1) * ... = 9. Given that 9 is a composite number, there are two primary cases for its prime factorization:

1. Case 1: (a1+1) = 9

This implies a1 = 8. So, N must be of the form p^8, where p is a prime number. Examples: 2^8 = 256, 3^8 = 6561.

1. Case 2: (a1+1) * (a2+1) = 9

Since 9 = 3 \* 3, this implies a1+1 = 3 and a2+1 = 3. So, a1 = 2 and a2 = 2. Thus, N must be of the form p1^2 * p2^2, where p1 and p2 are distinct prime numbers. Examples: 2^2 \* 3^2 = 4 \* 9 = 36, 2^2 \* 5^2 = 4 \* 25 = 100.

We will implement a solution that checks these two conditions for each number up to a given limit.

Approach 1: Iterating and Checking Divisors (Brute Force)

This approach directly counts divisors for each number up to the limit. While simple, it's inefficient for large limits.

// Count Numbers with Exactly 9 Divisors (Brute Force)
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {

    // Function to count divisors of a number
    public static int countDivisors(int n) {
        int count = 0;
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                if (i * i == n) {
                    count++;
                } else {
                    count += 2;
                }
            }
        }
        return count;
    }

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

        int numbersWithNineDivisors = 0;

        // Step 1: Iterate through each number from 1 to N
        for (int i = 1; i <= N; i++) {
            // Step 2: Count divisors for the current number
            int divisors = countDivisors(i);
            // Step 3: Check if the count is exactly 9
            if (divisors == 9) {
                numbersWithNineDivisors++;
                System.out.println(i + " has exactly 9 divisors.");
            }
        }

        System.out.println("Total numbers up to " + N + " with exactly 9 divisors: " + numbersWithNineDivisors);
    }
}

Run

Sample Output:

Enter the upper limit (N): 100
36 has exactly 9 divisors.
Total numbers up to 100 with exactly 9 divisors: 1

Stepwise Explanation:

1. The countDivisors function efficiently counts divisors by iterating up to the square root of n.
2. The main method takes an upper limit N from the user.
3. It then iterates from 1 to N.
4. For each number, it calls countDivisors to get the total divisor count.
5. If the count is 9, it increments a counter and prints the number.
6. Finally, it prints the total count.

Approach 2: Optimized Approach using Prime Factorization Properties

This approach leverages the properties derived from the number of divisors formula, making it much more efficient. It involves pre-calculating primes and then checking the two cases.

```java // Program Title: Count Numbers with Exactly 9 Divisors (Optimized) import java.util.ArrayList; import java.util.List; import java.util.Scanner;

// Main class containing the entry point of the program public class Main {

// Function to generate primes up to a limit using Sieve of Eratosthenes public static List<Integer> sieveOfEratosthenes(int limit) { boolean[] isPrime = new boolean[limit + 1]; for (int i = 0; i <= limit; i++) { isPrime[i] = true; } isPrime[0] = false; isPrime[1] = false;

for (int p = 2; p * p <= limit; p++) { if (isPrime[p]) { for (int i