Given a perfect square natural number N. The task is to find all the factors of N.
Examples
Input: N = 100
Output: 1 2 4 5 10 20 25 50 100Input: N = 900
Output: 1 2 4 3 6 12 9 18 36 5 10 20 15 30 60 45 90 180 25 50 100 75 150 300 225 450 900
Approach:
- Find the square root of N in temp.
- Find all the prime factors of temp in O(sqrt(temp)) using the approach discussed in this article.
- Initialise an array factor[] with element 1 in it.
- Store all the prime factors of temp obtained in above step twice in an array factor[].
- Initialise a matrix M such that for every element in factor[] starting from index 1:
- If factor[i] is equals to factor[i-1], then store factor[i]*factor[i-1] in matrix M in row i – 1 .
- Else factor[i] is not equals to factor[i-1], then store factor[i]*factor[i-1] in matrix M in row i.
- If factor[i] is equals to factor[i-1], then store factor[i]*factor[i-1] in matrix M in row i – 1 .
- Initialise two arrays arr1[] and arr2[] with the element 1 in both the array.
- Iterate over every row of matrix M such that the product of every element in arr1[] with every element of current row must be stored in arr2[].
- After above step, copy every element of arr2[] in arr1[].
- Repeat above two steps, till all the element of matrixM is traverse.
- The array arr2[] contains all the factors of number N.
Below is the implementation of the above approach:
C++
// C++ program to find the factors// of large perfect square number// in O(sqrt(sqrt(N))) time#include "bits/stdc++.h"using namespace std;int MAX = 100000;// Function that find all the prime// factors of Nvoid findFactors(int N){ // Store the sqrt(N) in temp int temp = sqrt(N); // Initialise factor array with // 1 as a factor in it int factor[MAX] = { 1 }; int i, j, k; int len1 = 1; // Check divisibility by 2 while (temp % 2 == 0) { // Store the factors twice factor[len1++] = 2; factor[len1++] = 2; temp /= 2; } // Check for other prime // factors other than 2 for (j = 3; j < sqrt(temp); j += 2) { // If j is a prime factor while (temp % j == 0) { // Store the prime // factor twice factor[len1++] = j; factor[len1++] = j; temp /= j; } } // If j is prime number left // other than 2 if (temp > 2) { // Store j twice factor[len1++] = temp; factor[len1++] = temp; } // Initialise Matrix M to // to store all the factors int M[len1][MAX] = { 0 }; // tpc for rows // tpr for column int tpc = 0, tpr = 0; // Initialise M[0][0] = 1 as // it also factor of N M[0][0] = 1; j = 1; // Traversing factor array while (j < len1) { // If current and previous // factors are not same then // move to next row and // insert the current factor if (factor[j] != factor[j - 1]) { tpr++; M[tpr][0] = factor[j]; j++; tpc = 1; } // If current and previous // factors are same then, // Insert the factor with // previous factor inserted // in matrix M else { M[tpr][tpc] = M[tpr][tpc - 1] * factor[j]; j++; tpc++; } } // The arr1[] and arr2[] used to // store all the factors of N int arr1[MAX], arr2[MAX]; int l1, l2; l1 = l2 = 1; // Initialise arrays as 1 arr1[0] = arr2[0] = 1; // Traversing the matrix M for (i = 1; i < tpr + 1; i++) { // Traversing till column // element doesn't become 0 for (j = 0; M[i][j] != 0; j++) { // Store the product of // every element of current // row with every element // in arr1[] for (k = 0; k < l1; k++) { arr2[l2++] = arr1[k] * M[i][j]; } } // Copying every element of // arr2[] in arr1[] for (j = l1; j < l2; j++) { arr1[j] = arr2[j]; } // length of arr2[] and arr1[] // are equal after copying l1 = l2; } // Print all the factors for (i = 0; i < l2; i++) { cout << arr2[i] << ' '; }}// Drivers Codeint main(){ int N = 900; findFactors(N); return 0;} |
Java
// Java program to find the factors// of large perfect square number// in O(Math.sqrt(Math.sqrt(N))) timeimport java.util.*;class GFG{ static int MAX = 100000; // Function that find all the prime// factors of Nstatic void findFactors(int N){ // Store the Math.sqrt(N) in temp int temp = (int) Math.sqrt(N); // Initialise factor array with // 1 as a factor in it int []factor = new int[MAX]; Arrays.fill(factor, 1); int i, j, k; int len1 = 1; // Check divisibility by 2 while (temp % 2 == 0) { // Store the factors twice factor[len1++] = 2; factor[len1++] = 2; temp /= 2; } // Check for other prime // factors other than 2 for (j = 3; j < Math.sqrt(temp); j += 2) { // If j is a prime factor while (temp % j == 0) { // Store the prime // factor twice factor[len1++] = j; factor[len1++] = j; temp /= j; } } // If j is prime number left // other than 2 if (temp > 2) { // Store j twice factor[len1++] = temp; factor[len1++] = temp; } // Initialise Matrix M to // to store all the factors int [][]M = new int[len1][MAX]; // tpc for rows // tpr for column int tpc = 0, tpr = 0; // Initialise M[0][0] = 1 as // it also factor of N M[0][0] = 1; j = 1; // Traversing factor array while (j < len1) { // If current and previous // factors are not same then // move to next row and // insert the current factor if (factor[j] != factor[j - 1]) { tpr++; M[tpr][0] = factor[j]; j++; tpc = 1; } // If current and previous // factors are same then, // Insert the factor with // previous factor inserted // in matrix M else { M[tpr][tpc] = M[tpr][tpc - 1] * factor[j]; j++; tpc++; } } // The arr1[] and arr2[] used to // store all the factors of N int []arr1 = new int[MAX]; int []arr2 = new int[MAX]; int l1, l2; l1 = l2 = 1; // Initialise arrays as 1 arr1[0] = arr2[0] = 1; // Traversing the matrix M for (i = 1; i < tpr + 1; i++) { // Traversing till column // element doesn't become 0 for (j = 0; M[i][j] != 0; j++) { // Store the product of // every element of current // row with every element // in arr1[] for (k = 0; k < l1; k++) { arr2[l2++] = arr1[k] * M[i][j]; } } // Copying every element of // arr2[] in arr1[] for (j = l1; j < l2; j++) { arr1[j] = arr2[j]; } // length of arr2[] and arr1[] // are equal after copying l1 = l2; } // Print all the factors for (i = 0; i < l2; i++) { System.out.print(arr2[i] + " "); }} // Drivers Codepublic static void main(String[] args){ int N = 900; findFactors(N);}}// This code is contributed by sapnasingh4991 |
Python3
# Python 3 program to find the factors# of large perfect square number# in O(sqrt(sqrt(N))) time import mathMAX = 100000 # Function that find all the prime# factors of Ndef findFactors( N): # Store the sqrt(N) in temp temp = int(math.sqrt(N)) # Initialise factor array with # 1 as a factor in it factor = [1]*MAX len1 = 1 # Check divisibility by 2 while (temp % 2 == 0) : # Store the factors twice factor[len1] = 2 len1 += 1 factor[len1] = 2 len1 += 1 temp //= 2 # Check for other prime # factors other than 2 sqt = math.sqrt(temp) for j in range(3, math.ceil(sqt), 2): # If j is a prime factor while (temp % j == 0): # Store the prime # factor twice factor[len1] = j len1 += 1 factor[len1] = j len1 += 1 temp //= j # If j is prime number left # other than 2 if (temp > 2) : # Store j twice factor[len1] = temp len1 += 1 factor[len1] = temp len1 += 1 # Initialise Matrix M to # to store all the factors M = [ [ 0 for x in range(MAX)] for y in range(len1)] # tpc for rows # tpr for column tpc , tpr = 0 , 0 # Initialise M[0][0] = 1 as # it also factor of N M[0][0] = 1 j = 1 # Traversing factor array while (j < len1): # If current and previous # factors are not same then # move to next row and # insert the current factor if (factor[j] != factor[j - 1]): tpr+=1 M[tpr][0] = factor[j] j += 1 tpc = 1 # If current and previous # factors are same then, # Insert the factor with # previous factor inserted # in matrix M else : M[tpr][tpc]= M[tpr][tpc - 1] * factor[j] j += 1 tpc += 1 # The arr1[] and arr2[] used to # store all the factors of N arr1 = [0]*MAX arr2 = [0]*MAX l1 = l2 = 1 # Initialise arrays as 1 arr1[0] = 1 arr2[0] = 1 # Traversing the matrix M # print("tpr ",tpr) for i in range(1 , tpr + 1) : # Traversing till column # element doesn't become 0 j = 0 while M[i][j] != 0: # Store the product of # every element of current # row with every element # in arr1[] for k in range(l1): arr2[l2]= arr1[k] * M[i][j] l2 += 1 j += 1 # Copying every element of # arr2[] in arr1[] for j in range(l1, l2): arr1[j] = arr2[j] # length of arr2[] and arr1[] # are equal after copying l1 = l2 # Print all the factors for i in range(l2): print(arr2[i] ,end= " ") # Drivers Codeif __name__ == "__main__": N = 900 findFactors(N) # This code is contributed by chitranayal |
C#
// C# program to find the factors// of large perfect square number// in O(Math.Sqrt(Math.Sqrt(N))) timeusing System;class GFG{static int MAX = 100000;// Function that find all the prime// factors of Nstatic void findFactors(int N){ // Store the Math.Sqrt(N) in temp int temp = (int) Math.Sqrt(N); // Initialise factor array with // 1 as a factor in it int []factor = new int[MAX]; for(int l= 0; l < MAX; l++) factor[l] = 1; int i, j, k; int len1 = 1; // Check divisibility by 2 while (temp % 2 == 0) { // Store the factors twice factor[len1++] = 2; factor[len1++] = 2; temp /= 2; } // Check for other prime // factors other than 2 for (j = 3; j < Math.Sqrt(temp); j += 2) { // If j is a prime factor while (temp % j == 0) { // Store the prime // factor twice factor[len1++] = j; factor[len1++] = j; temp /= j; } } // If j is prime number left // other than 2 if (temp > 2) { // Store j twice factor[len1++] = temp; factor[len1++] = temp; } // Initialise Matrix M to // to store all the factors int [,]M = new int[len1, MAX]; // tpc for rows // tpr for column int tpc = 0, tpr = 0; // Initialise M[0,0] = 1 as // it also factor of N M[0, 0] = 1; j = 1; // Traversing factor array while (j < len1) { // If current and previous // factors are not same then // move to next row and // insert the current factor if (factor[j] != factor[j - 1]) { tpr++; M[tpr, 0] = factor[j]; j++; tpc = 1; } // If current and previous // factors are same then, // Insert the factor with // previous factor inserted // in matrix M else { M[tpr,tpc] = M[tpr,tpc - 1] * factor[j]; j++; tpc++; } } // The arr1[] and arr2[] used to // store all the factors of N int []arr1 = new int[MAX]; int []arr2 = new int[MAX]; int l1, l2; l1 = l2 = 1; // Initialise arrays as 1 arr1[0] = arr2[0] = 1; // Traversing the matrix M for (i = 1; i < tpr + 1; i++) { // Traversing till column // element doesn't become 0 for (j = 0; M[i, j] != 0; j++) { // Store the product of // every element of current // row with every element // in arr1[] for (k = 0; k < l1; k++) { arr2[l2++] = arr1[k] * M[i, j]; } } // Copying every element of // arr2[] in arr1[] for (j = l1; j < l2; j++) { arr1[j] = arr2[j]; } // length of arr2[] and arr1[] // are equal after copying l1 = l2; } // Print all the factors for (i = 0; i < l2; i++) { Console.Write(arr2[i] + " "); }}// Drivers Codepublic static void Main(String[] args){ int N = 900; findFactors(N);}}// This code is contributed by sapnasingh4991 |
Javascript
<script>// Javascript program to find the factors// of large perfect square number// in O(Math.sqrt(Math.sqrt(N))) timelet MAX = 100000;// Function that find all the prime// factors of Nfunction findFactors(N){ // Store the Math.sqrt(N) in temp let temp = Math.floor(Math.sqrt(N)); // Initialise factor array with // 1 as a factor in it let factor = new Array(MAX); for(let i = 0; i < MAX; i++) { factor[i] = 1; } let i, j, k; let len1 = 1; // Check divisibility by 2 while (temp % 2 == 0) { // Store the factors twice factor[len1++] = 2; factor[len1++] = 2; temp = Math.floor(temp / 2); } // Check for other prime // factors other than 2 for(j = 3; j < Math.sqrt(temp); j += 2) { // If j is a prime factor while (temp % j == 0) { // Store the prime // factor twice factor[len1++] = j; factor[len1++] = j; temp = Math.floor(temp / j); } } // If j is prime number left // other than 2 if (temp > 2) { // Store j twice factor[len1++] = temp; factor[len1++] = temp; } // Initialise Matrix M to // to store all the factors let M = new Array(len1); for(let i = 0; i < len1; i++) { M[i] = new Array(MAX); for(let j = 0; j < MAX; j++) { M[i][j] = 0; } } // tpc for rows // tpr for column let tpc = 0, tpr = 0; // Initialise M[0][0] = 1 as // it also factor of N M[0][0] = 1; j = 1; // Traversing factor array while (j < len1) { // If current and previous // factors are not same then // move to next row and // insert the current factor if (factor[j] != factor[j - 1]) { tpr++; M[tpr][0] = factor[j]; j++; tpc = 1; } // If current and previous // factors are same then, // Insert the factor with // previous factor inserted // in matrix M else { M[tpr][tpc] = M[tpr][tpc - 1] * factor[j]; j++; tpc++; } } // The arr1[] and arr2[] used to // store all the factors of N let arr1 = new Array(MAX); let arr2 = new Array(MAX); for(let i = 0; i < MAX; i++) { arr1[i] = 0; arr2[i] = 0; } let l1, l2; l1 = l2 = 1; // Initialise arrays as 1 arr1[0] = arr2[0] = 1; // Traversing the matrix M for(i = 1; i < tpr + 1; i++) { // Traversing till column // element doesn't become 0 for(j = 0; M[i][j] != 0; j++) { // Store the product of // every element of current // row with every element // in arr1[] for(k = 0; k < l1; k++) { arr2[l2++] = arr1[k] * M[i][j]; } } // Copying every element of // arr2[] in arr1[] for(j = l1; j < l2; j++) { arr1[j] = arr2[j]; } // length of arr2[] and arr1[] // are equal after copying l1 = l2; } // Print all the factors for(i = 0; i < l2; i++) { document.write(arr2[i] + " "); }}// Driver Codelet N = 900;findFactors(N);// This code is contributed by avanitrachhadiya2155</script> |
Output
1 2 4 3 6 12 9 18 36 5 10 20 15 30 60 45 90 180 25 50 100 75 150 300 225 450 900
Time Complexity: O(sqrt(sqrt(N)))
Auxiliary Space: O(MAX)
Method: “Naive Factorization Method”
- Initialize an empty vector called factors to store the factors of N.
- Loop through all the numbers from 1 to sqrt(N). For each number i, check if N is divisible by i (i.e., N % i == 0). If it is, then i is a factor of N.
- Add i to the vector factors. If i is not equal to the quotient N/i (i.e., i != N/i), then add N/i to the vector factors as well. This is done to avoid adding duplicate factors to the vector.
- Once all the factors have been added to the vector factors, print all the elements in the vector to get all the factors of N.
- Since we loop only till sqrt(N), the time complexity of this algorithm is O(sqrt(sqrt(N))).
C++
#include <iostream>#include <vector>using namespace std;void findFactors(int n) { vector<int> factors; // to store factors of n for (int i = 1; i*i <= n; i++) { if (n % i == 0) { factors.push_back(i); if (i != n/i) { // to avoid duplicates factors.push_back(n/i); } } } // print factors for (int i = 0; i < factors.size(); i++) { cout << factors[i] << " "; } cout << endl;}int main() { int N1 = 100, N2 = 900; cout << "Factors of " << N1 << " are: "; findFactors(N1); cout << "Factors of " << N2 << " are: "; findFactors(N2); return 0;} |
Java
import java.util.ArrayList;import java.util.List;class Main { static void findFactors(int n) { List<Integer> factors = new ArrayList<>(); // to store factors of n for (int i = 1; i * i <= n; i++) { if (n % i == 0) { factors.add(i); if (i != n / i) { // to avoid duplicates factors.add(n / i); } } } // print factors for (int i = 0; i < factors.size(); i++) { System.out.print(factors.get(i) + " "); } System.out.println(); } public static void main(String[] args) { int N1 = 100, N2 = 900; System.out.print("Factors of " + N1 + " are: "); findFactors(N1); System.out.print("Factors of " + N2 + " are: "); findFactors(N2); }} |
Python3
def find_factors(n): factors = [] # to store factors of n for i in range(1, int(n**0.5)+1): if n % i == 0: factors.append(i) if i != n // i: # to avoid duplicates factors.append(n // i) # print factors for factor in factors: print(factor, end=' ') print()N1, N2 = 100, 900print(f"Factors of {N1} are: ", end='')find_factors(N1)print(f"Factors of {N2} are: ", end='')find_factors(N2) |
C#
using System;using System.Collections.Generic;class Program { static void Main() { int N1 = 100, N2 = 900; Console.Write("Factors of {0} are: ", N1); FindFactors(N1); Console.Write("Factors of {0} are: ", N2); FindFactors(N2); } static void FindFactors(int n) { List<int> factors = new List<int>(); // to store factors of n for (int i = 1; i * i <= n; i++) { if (n % i == 0) { factors.Add(i); if (i != n / i) // to avoid duplicates { factors.Add(n / i); } } } // print factors foreach(int factor in factors) { Console.Write(factor + " "); } Console.WriteLine(); }} |
Javascript
var findFactors = function(n) {var factors = []; // to store factors of nfor (var i = 1; i * i <= n; i++) {if (n % i == 0) {factors.push(i);if (i != n / i) { // to avoid duplicatesfactors.push(n / i);}}}// print factorsfor (var i = 0; i < factors.length; i++) {console.log(factors[i] + " ");}console.log();}var N1 = 100, N2 = 900;console.log("Factors of " + N1 + " are: ");findFactors(N1);console.log("Factors of " + N2 + " are: ");findFactors(N2);// This code is contributed by sarojmcy2e |
Output
Factors of 100 are: 1 100 2 50 4 25 5 20 10 Factors of 900 are: 1 900 2 450 3 300 4 225 5 180 6 150 9 100 10 90 12 75 15 60 18 50 20 45 25 36 30
The time complexity of the given approach is O(sqrt(sqrt(N)))
The auxiliary space used by the algorithm is O(sqrt(sqrt(N))
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!
