Find the maximum power of a number that divides a factorial in Java

Introduction:

Factorials and prime numbers play key roles in counting arrangements and comprehending number qualities, making them extremely important in mathematics and computer science. The sum of all positive integers from 1 to 'n' is known as a factorial of a non-negative integer 'n,' symbolized as 'n!'. Integers bigger than 1 that have only themselves and the number 1 as their only positive divisors are known as prime numbers.

Approach: Prime Factorization

A positive integer is expressed as the product of its prime factors through the prime factorization method. The sum of its prime factors may singularly represent every positive number greater than one.

Example:

Let us take an example where n = 20 and p = 2. Find the maximum power of the prime number 2 that divides 20!

In this approach, we calculate the prime factorization of each number from 1 to 20 and count the occurrences of the prime factor 2.

Prime factorization of 20! :

20! = 2^18 * 3^8 * 5^4 * 7^2 * 11^1 * 13^1 * 17^1 * 19^1

Occurrences of the prime factor 2: 18

Algorithm:

Step 1: Make a prime factorization function that accepts the integer 'num' as an argument.

Step 2: To hold the number of prime factors for each number, initialize an integer array called primeCounts with the size 'num + 1'.

Step 3: Iterate through each number 'i' from 2 to 'num':

Step 3.1: Dеclarе a local variablе callеd "n" and sеt it to thе valuе of "i." The prime factorization process will make use of this variable.

Step 3.2: Starting with number two, go through all prime factor j, divide 'n' by 'j' when 'n' is divisible by 'j,' and then raise the value of 'j' in the primeCounts array.

Step 3.3: If 'n' is still greater than 1 after the loop, increase the n count in the primeCounts array.

Step 4: Create a maxPowerOfPrimeInFactorial function that accepts the inputs "n" and "p" as two integers.

Step 5: To obtain the primeCounts array, use the 'n' argument when calling the prime factorization function. The value stored at index "p" in the primeCounts array is the highest power of "p" that divides "n! ".

Filename: MaxPowerOfPrimeInFactorial.java

public class MaxPowerOfPrimeInFactorial {

    // Function to calculate the prime factorization of a number

    static int[] primeFactorization(int num) {

        int[] primeCounts = new int[num + 1];

        for (int i = 2; i <= num; i++) {

            int n = i;

            for (int j = 2; j * j <= n; j++) {

                while (n % j == 0) {

                    primeCounts[j]++;

                    n /= j;

                }

            }

            if (n > 1) {

                primeCounts[n]++;

            }

        } 

        return primeCounts;

    }

    // Function to find the maximum power of a prime factor 'p' in 'n!'

    static int maxPowerOfPrimeInFactorial(int n, int p) {

        int[] primeCounts = primeFactorization(n);

        return primeCounts[p];

    }

    public static void main(String[] args) {

        int n = 10; // Replace with your desired value of 'n'

        int p = 2;  // Replace with your desired prime factor   

        int maxPower = maxPowerOfPrimeInFactorial(n, p);

        System.out.println("The maximum power of " + p + " that divides " + n + "! is: " + maxPower);

    }

}

Output:

The maximum power of 2 divides 10! is: 8

Time Complexity:

The total number of operations for the prime factorization function can be approximated as the sum of the series of the square root of each number from 2 to 'num':

T(n) = sqrt(2) + sqrt(3) + ... + sqrt(n)    

This series grows slower than a linear series. The most time-consuming part of the code is the primeFactorization function, which dominates the time complexity.

Hence, the time complexity can be approximated as O(n * sqrt(n)).

Space Complexity:

The function uses an integer array of primeCounts of size 'num + 1' to store prime counts for each number up to 'num'.

Hence, the space complexity is O(n).

Approach: Using floor division

Using a mathematical formula utilizing the idea of floor division is one method of determining the most significant power of a prime number that divides a factorial. This method is founded on discovering that the formula may be used to compute the most significant power of a prime p that divides n!

maxPower = floor(n/p) + floor(n/p^2) + floor(n/p^3) + ...     

Where "floor(x)" stands for the most significant number less than or equal to "x" and "pi" stands for the "i" -th power of the prime "p."

Example:

Let us take an example where n=20 and p=2. Find the maximum power of prime number 2 that divides 20!

In this approach, we use the formula to calculate the maximum power of the prime factor 2 that divides 20!:

maxPower = floor(n/p) + floor(n/p^2) + floor(n/p^3) + ...    

Plugging in 'n' = 20 and 'p' = 2

maxPower = floor(20/2) + floor(20/2^2) + floor(20/2^3) + ... = 10 + 5 + 2 + 1 = 18

Occurrences of the prime factor 2: 18

Algorithm:

Step 1: Set maxPower to a value of 0. This variable will hold the highest possible power of the prime factor "p" that divides the factorial "n!"

Step 2: Set the value of powerOfP to 'p'. This variable will record the prime factor 'p' powers being considered.

Step 3: Make the following selections when power is less than or equal to 'n':

Step 3.1: Increase maxPower by the amount obtained by multiplying the floor value of 'n' by the powerOfP. This explains how the current power of 'p' contributed to the overall count of 'p' in the prime factorization of 'n!'.

Step 3.2: Divide powerOfP by 'p.' This raises powerOfP to the subsequent power of "p."

Step 4: After the loop is complete, the max power value will reflect the most incredible power of "p" that divides "n!"

Filename: MaxPowerOfPrimeInFactorialFormula.java

public class MaxPowerOfPrimeInFactorialFormula {   

    // Function to find the maximum power of a prime factor 'p' in 'n!'

    static int maxPowerOfPrimeInFactorial(int n, int p) {

        int maxPower = 0;

        int powerOfP = p;       

        while (powerOfP <= n) {

            maxPower += n / powerOfP;

            powerOfP *= p;

        }       

        return maxPower;

    }   

    public static void main(String[] args) {

        int n = 25; // Replace with your desired value of 'n'

        int p = 5;  // Replace with your desired prime factor       

        int maxPower = maxPowerOfPrimeInFactorial(n, p);

        System.out.println("The maximum power of " + p + " that divides " + n + "! is: " + maxPower);

    }

}

Output:

The maximum power of 5 divides 25! is: 6

Explanation:

• A while loop runs as long as the current power of 'p' (powerOfP) is less than or equal to 'n'.
• Inside the loop: The value of maxPower is updated by adding the floor division of 'n' by the current power of 'p.' powerOfP is multiplied by 'p,' increasing the power to the next level.
• The loop continues until the condition is no longer met, ensuring that all relevant powers of 'p' within 'n' are considered.

Time Complexity:

The while loop runs as long as powerOfP is less than or equal to 'n'. In each iteration, the value of powerOfP is multiplied by 'p'. The number of iterations in the while loop determines how many times 'p' needs to be multiplied to become greater than 'n.' This can be calculated as the logarithm base 'p' of 'n,' roughly O(log_p n).

Hence, the time complexity is O(log_p n)

Space Complexity:

The function uses a constant amount of memory for integer variables (maxPower and powerOfP), which results in O(1) space complexity. The main function also uses constant memory for variables, leading to O(1) space complexity.

Hence, the space complexity is O(1).