Given an array arr[] of n positive integers. Represent every number as its factors (x * y = arr[i]) [Here x or y cannot be 1] till it cannot be further represented as x*y = arr[i]. Print the number of steps required to split it till no further representations are possible.
Examples:
Input: 4 4 4
Output: 3
Explanation: 1st step 2 2 4 4 .
2nd step 2 2 2 2 4
3rd step 2 2 2 2 2 2
Input: 20 4
Output: 3
Explanation: 1st step 20 2 2 (2*2 = 4)
2nd step 2 10 2 2 (2*10 = 20)
3rd step 2 2 5 2 2, (2*5 = 10)
Approach is to pre calculate the prime factors of every number. Prime factors can be efficiently calculated using Sieve’s implementation which requires N * log N. . We know a number can be represented as a multiplication of its prime factors and we can represent it till its not 1, so 1 is not taken into count, so if the number is other than 1, we count the number of prime factors, and then subtract 1 from it.
Implementation:
C++
// CPP program to count number of steps // required to convert an integer array // to array of factors. #include <iostream> using namespace std; const int MAX = 1000001; // array to store prime factors int factor[MAX] = { 0 }; // function to generate all prime factors // of numbers from 1 to 10^6 void cal_factor() { factor[1] = 1; // Initializes all the positions with their value. for (int i = 2; i < MAX; i++) factor[i] = i; // Initializes all multiples of 2 with 2 for (int i = 4; i < MAX; i += 2) factor[i] = 2; // A modified version of Sieve of Eratosthenes to // store the smallest prime factor that divides // every number. for (int i = 3; i * i < MAX; i++) { // check if it has no prime factor. if (factor[i] == i) { // Initializes of j starting from i*i for (int j = i * i; j < MAX; j += i) { // if it has no prime factor before, then // stores the smallest prime divisor if (factor[j] == j) factor[j] = i; } } } } // function to calculate the number of representations int no_of_representations(int a[], int n) { // keep an count of prime factors int count = 0; // traverse for every element for (int i = 0; i < n; i++) { int temp = a[i]; int flag = 0; // count the no of factors while (factor[temp] != 1) { flag = -1; count++; temp = temp / factor[temp]; } // subtract 1 if Ai is not 1 as the last step // wont be taken into count count += flag; } return count; } // driver program to test the above function int main() { // call sieve to calculate the factors cal_factor(); int a[] = { 4, 4, 4 }; int n = sizeof(a) / sizeof(a[0]); cout << no_of_representations(a, n); return 0; } |
Java
// Java program to count number of steps // required to convert an integer array // to array of factors. class GFG { static final int MAX = 1000001; // array to store prime factors static int factor[] = new int[MAX]; // function to generate all prime factors // of numbers from 1 to 10^6 static void cal_factor() { factor[1] = 1; // Initializes all the positions // with their value. for (int i = 2; i < MAX; i++) factor[i] = i; // Initializes all multiples of 2 with 2 for (int i = 4; i < MAX; i += 2) factor[i] = 2; // A modified version of Sieve of Eratosthenes to // store the smallest prime factor that divides // every number. for (int i = 3; i * i < MAX; i++) { // check if it has no prime factor. if (factor[i] == i) { // Initializes of j starting from i*i for (int j = i * i; j < MAX; j += i) { // if it has no prime factor before, then // stores the smallest prime divisor if (factor[j] == j) factor[j] = i; } } } } // function to calculate the // number of representations static int no_of_representations(int a[], int n) { // keep an count of prime factors int count = 0; // traverse for every element for (int i = 0; i < n; i++) { int temp = a[i]; int flag = 0; // count the no of factors while (factor[temp] != 1) { flag = -1; count++; temp = temp / factor[temp]; } // subtract 1 if Ai is not 1 as the // last step wont be taken into count count += flag; } return count; } // Driver code public static void main(String[] args) { // call sieve to calculate the factors cal_factor(); int a[] = {4, 4, 4}; int n = a.length; System.out.print(no_of_representations(a, n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python 3 program to count number # of steps required to convert an # integer array to array of factors. MAX = 1000001 # array to store prime factors factor = [0] * MAX # function to generate all prime # factors of numbers from 1 to 10^6 def cal_factor(): factor[1] = 1 # Initializes all the positions # with their value. for i in range(2, MAX): factor[i] = i # Initializes all multiples # of 2 with 2 for i in range(4, MAX, 2): factor[i] = 2 # A modified version of Sieve of # Eratosthenes to store the smallest # prime factor that divides every number. i = 3 while i * i < MAX: # check if it has no prime factor. if (factor[i] == i) : # Initializes of j starting # from i*i for j in range(i * i, MAX, i) : # if it has no prime factor # before, then stores the # smallest prime divisor if (factor[j] == j): factor[j] = i i += 1 # function to calculate the # number of representations def no_of_representations(a, n): # keep an count of prime factors count = 0 # traverse for every element for i in range(n) : temp = a[i] flag = 0 # count the no of factors while (factor[temp] != 1) : flag = -1 count += 1 temp = temp // factor[temp] # subtract 1 if Ai is not 1 as the # last step wont be taken into count count += flag return count # Driver Code if __name__ == "__main__": # call sieve to calculate the factors cal_factor() a = [ 4, 4, 4 ] n = len(a) print(no_of_representations(a, n)) # This code is contributed # by ChitraNayal |
C#
// C# program to count number of steps // required to convert an integer array // to array of factors. using System; class GFG { static int MAX = 1000001; // array to store prime factors static int []factor = new int[MAX]; // function to generate all prime // factors of numbers from 1 to 10^6 static void cal_factor() { factor[1] = 1; // Initializes all the positions // with their value. for (int i = 2; i < MAX; i++) factor[i] = i; // Initializes all multiples of // 2 with 2 for (int i = 4; i < MAX; i += 2) factor[i] = 2; // A modified version of Sieve of // Eratosthenes to store the // smallest prime factor that // divides every number. for (int i = 3; i * i < MAX; i++) { // check if it has no prime // factor. if (factor[i] == i) { // Initializes of j // starting from i*i for (int j = i * i; j < MAX; j += i) { // if it has no prime // factor before, then // stores the smallest // prime divisor if (factor[j] == j) factor[j] = i; } } } } // function to calculate the // number of representations static int no_of_representations( int []a, int n) { // keep an count of prime factors int count = 0; // traverse for every element for (int i = 0; i < n; i++) { int temp = a[i]; int flag = 0; // count the no of factors while (factor[temp] != 1) { flag = -1; count++; temp = temp / factor[temp]; } // subtract 1 if Ai is not 1 // as the last step wont be // taken into count count += flag; } return count; } // Driver code public static void Main() { // call sieve to calculate // the factors cal_factor(); int []a = {4, 4, 4}; int n = a.Length; Console.WriteLine( no_of_representations(a, n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to count number of steps // required to convert an integer array // to array of factors. $MAX = 100001; // array to store prime factors $factor = array_fill(0, $MAX + 1, 0); // function to generate all prime // factors of numbers from 1 to 10^6 function cal_factor() { global $factor, $MAX; $factor[1] = 1; // Initializes all the positions // with their value. for ($i = 2; $i < $MAX; $i++) $factor[$i] = $i; // Initializes all multiples of 2 with 2 for ($i = 4; $i < $MAX; $i += 2) $factor[$i] = 2; // A modified version of Sieve of // Eratosthenes to store the smallest // prime factor that divides every number. for ($i = 3; $i * $i < $MAX; $i++) { // check if it has no prime factor. if ($factor[$i] == $i) { // Initializes of j starting from i*i for ($j = $i * $i; $j < $MAX; $j += $i) { // if it has no prime factor before, then // stores the smallest prime divisor if ($factor[$j] == $j) $factor[$j] = $i; } } } } // function to calculate the // number of representations function no_of_representations($a, $n) { global $factor, $MAX; // keep an count of prime factors $count = 0; // traverse for every element for ($i = 0; $i < $n; $i++) { $temp = $a[$i]; $flag = 0; // count the no of factors while ($factor[$temp] != 1) { $flag = -1; $count++; $temp = (int)($temp / $factor[$temp]); } // subtract 1 if Ai is not 1 as the // last step wont be taken into count $count += $flag; } return $count; } // Driver Code // call sieve to calculate the factors cal_factor(); $a = array( 4, 4, 4 ); $n = count($a); echo no_of_representations($a, $n); // This code is contributed by mits ?> |
Javascript
<script> // Javascript program to count number of steps // required to convert an integer array // to array of factors. let MAX = 1000001; // array to store prime factors let factor = []; // function to generate all prime factors // of numbers from 1 to 10^6 function cal_factor() { factor[1] = 1; // Initializes all the positions // with their value. for (let i = 2; i < MAX; i++) factor[i] = i; // Initializes all multiples of 2 with 2 for (let i = 4; i < MAX; i += 2) factor[i] = 2; // A modified version of Sieve of Eratosthenes to // store the smallest prime factor that divides // every number. for (let i = 3; i * i < MAX; i++) { // check if it has no prime factor. if (factor[i] == i) { // Initializes of j starting from i*i for (let j = i * i; j < MAX; j += i) { // if it has no prime factor before, then // stores the smallest prime divisor if (factor[j] == j) factor[j] = i; } } } } // function to calculate the // number of representations function no_of_representations(a, n) { // keep an count of prime factors let count = 0; // traverse for every element for (let i = 0; i < n; i++) { let temp = a[i]; let flag = 0; // count the no of factors while (factor[temp] != 1) { flag = -1; count++; temp = temp / factor[temp]; } // subtract 1 if Ai is not 1 as the // last step wont be taken into count count += flag; } return count; } // Driver code // call sieve to calculate the factors cal_factor(); let a = [4, 4, 4]; let n = a.length; document.write(no_of_representations(a, n)); // This code is contributed by code_hunt. </script> |
Output
3
Time Complexity: O(N*logN), as the first two for loops we are using will cost us O(Max), then we are using nested loops in cal_factor function which will cost use O(Max*sqrt(Max)) and we are using nested loops in number_of_representations function where outer for loop will traverse N times and inner while loop will traverse logN time and each time we are decrementing by factor division.
Auxiliary Space: O(1000001), as we are using extra space for factor.
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
