# Count of multiplicative partitions of N

Given an integer **N**, the task is to find the total number of multiplicative partitions for N.

Multiplicative Partition:Number of ways of factoring of an integer with all factors greater than 1.

**Examples:**

Input:N = 20Output:4Explanation:

Multiplicative partitions of 20 are:

2 × 2 × 5 = 2 × 10 = 4 × 5 = 20.Input:N = 30Output:5Explanation:

Multiplicative partitions of 30 are:

2 × 3 × 5 = 2 × 15 = 6 × 5 = 3 × 10 = 30

**Approach**: The idea is to try for every divisor of the N and then recursively break the dividend to get the multiplicative partitions. Below are the illustrations of the steps of the approach:

- Initialize minimum factor as 2. Since it is the minimum factor other than 1.
- Start a loop from i = minimum to N – 1, and check if the number divides N and N/i > i, then increment the counter by 1 and again call the same function. Since i divides n so it means i and N/i can be factorized some more times.

**For Example:**

If N = 30, let i = min = 2

30 % 2 = 0, so again recur with (2, 15)

15 % 3 = 0, so again recur with (3, 5)

.

.

and so on.

Below is the implementation of the above approach:

## C++

`// C++ implementation to find` `// the multiplicative partitions of` `// the given number N` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to return number of ways` `// of factoring N with all` `// factors greater than 1` `static` `int` `getDivisors(` `int` `min, ` `int` `n)` `{` ` ` ` ` `// Variable to store number of ways` ` ` `// of factoring n with all` ` ` `// factors greater than 1` ` ` `int` `total = 0;` ` ` ` ` `for` `(` `int` `i = min; i < n; ++i)` ` ` `{` ` ` `if` `(n % i == 0 && n / i >= i)` ` ` `{` ` ` `++total;` ` ` `if` `(n / i > i)` ` ` `total += getDivisors(i, n / i);` ` ` `}` ` ` `}` ` ` `return` `total;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `n = 30;` ` ` ` ` `// 2 is the minimum factor of` ` ` `// number other than 1.` ` ` `// So calling recursive` ` ` `// function to find` ` ` `// number of ways of factoring N` ` ` `// with all factors greater than 1` ` ` `cout << 1 + getDivisors(2, n);` ` ` ` ` `return` `0;` `}` `// This code is contributed by rutvik_56` |

## Java

`// Java implementation to find` `// the multiplicative partitions of` `// the given number N` `class` `MultiPart {` ` ` `// Function to return number of ways` ` ` `// of factoring N with all` ` ` `// factors greater than 1` ` ` `static` `int` `getDivisors(` `int` `min, ` `int` `n)` ` ` `{` ` ` `// Variable to store number of ways` ` ` `// of factoring n with all` ` ` `// factors greater than 1` ` ` `int` `total = ` `0` `;` ` ` `for` `(` `int` `i = min; i < n; ++i)` ` ` `if` `(n % i == ` `0` `&& n / i >= i) {` ` ` `++total;` ` ` `if` `(n / i > i)` ` ` `total` ` ` `+= getDivisors(` ` ` `i, n / i);` ` ` `}` ` ` `return` `total;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `n = ` `30` `;` ` ` `// 2 is the minimum factor of` ` ` `// number other than 1.` ` ` `// So calling recursive` ` ` `// function to find` ` ` `// number of ways of factoring N` ` ` `// with all factors greater than 1` ` ` `System.out.println(` ` ` `1` `+ getDivisors(` `2` `, n));` ` ` `}` `}` |

## Python3

`# Python3 implementation to find` `# the multiplicative partitions of` `# the given number N` `# Function to return number of ways` `# of factoring N with all` `# factors greater than 1` `def` `getDivisors(` `min` `, n):` ` ` ` ` `# Variable to store number of ways` ` ` `# of factoring n with all` ` ` `# factors greater than 1` ` ` `total ` `=` `0` ` ` `for` `i ` `in` `range` `(` `min` `, n):` ` ` `if` `(n ` `%` `i ` `=` `=` `0` `and` `n ` `/` `/` `i >` `=` `i):` ` ` `total ` `+` `=` `1` ` ` `if` `(n ` `/` `/` `i > i):` ` ` `total ` `+` `=` `getDivisors(i, n ` `/` `/` `i)` ` ` ` ` `return` `total` `# Driver code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` ` ` `n ` `=` `30` ` ` `# 2 is the minimum factor of` ` ` `# number other than 1.` ` ` `# So calling recursive` ` ` `# function to find` ` ` `# number of ways of factoring N` ` ` `# with all factors greater than 1` ` ` `print` `(` `1` `+` `getDivisors(` `2` `, n))` `# This code is contributed by mohit kumar 29` |

## C#

`// C# implementation to find` `// the multiplicative partitions of` `// the given number N` `using` `System;` `class` `GFG{` ` ` `// Function to return number of ways` `// of factoring N with all` `// factors greater than 1` `static` `int` `getDivisors(` `int` `min, ` `int` `n)` `{` ` ` `// Variable to store number of ways` ` ` `// of factoring n with all` ` ` `// factors greater than 1` ` ` `int` `total = 0;` ` ` `for` `(` `int` `i = min; i < n; ++i)` ` ` `if` `(n % i == 0 && n / i >= i)` ` ` `{` ` ` `++total;` ` ` `if` `(n / i > i)` ` ` `total+= getDivisors(i, n / i);` ` ` `}` ` ` `return` `total;` `}` `// Driver code` `public` `static` `void` `Main()` `{` ` ` `int` `n = 30;` ` ` `// 2 is the minimum factor of` ` ` `// number other than 1.` ` ` `// So calling recursive` ` ` `// function to find` ` ` `// number of ways of factoring N` ` ` `// with all factors greater than 1` ` ` `Console.Write(1 + getDivisors(2, n));` `}` `}` `// This code is contributed by adityakumar27200` |

## Javascript

`<script>` `// Javascript implementation to find` `// the multiplicative partitions of` `// the given number N` `// Function to return number of ways` `// of factoring N with all` `// factors greater than 1` `function` `getDivisors(min, n)` `{` ` ` ` ` `// Variable to store number of ways` ` ` `// of factoring n with all` ` ` `// factors greater than 1` ` ` `var` `total = 0;` ` ` ` ` `for` `(` `var` `i = min; i < n; ++i)` ` ` `{` ` ` `if` `(n % i == 0 && n / i >= i)` ` ` `{` ` ` `++total;` ` ` `if` `(n / i > i)` ` ` `total += getDivisors(i, n / i);` ` ` `}` ` ` `}` ` ` `return` `total;` `}` `// Driver code` `var` `n = 30;` `// 2 is the minimum factor of` `// number other than 1.` `// So calling recursive` `// function to find` `// number of ways of factoring N` `// with all factors greater than 1` `document.write( 1 + getDivisors(2, n));` `</script>` |

**Output:**

5

**Time Complexity: **O(n)

**Auxiliary Space: **O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.