Find the total number of composite factor for a given number
Given an integer N, the task is to find the total number of composite factors of N. Composite factors of a number are the factors which are not prime.
Examples:
Input: N = 24
Output: 5
1, 2, 3, 4, 6, 8, 12 and 24 are the factors of 24.
Out of which only 4, 6, 8, 12 and 24 are composites.
Input: N = 100
Output: 6
Approach:
- Find all the factors of N and store it in a variable totalFactors
- Find all the prime factors of N and store it in a variable primeFactors
- Now, total composite factors will be totalFactors – primeFactors – 1 (1 is subtracted because 1 is neither prime nor composite).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the count // of prime factors of n int composite_factors( int n) { int count = 0; int i, j; // Initialise array with 0 int a[n + 1] = { 0 }; for (i = 1; i <= n; ++i) { if (n % i == 0) { // Stored i value into an array a[i] = i; } } // Every non-zero value at a[i] denotes // that i is a factor of n for (i = 2; i <= n; i++) { j = 2; int p = 1; // Find if i is prime while (j < a[i]) { if (a[i] % j == 0) { p = 0; break ; } j++; } // If i is a factor of n // and i is not prime if (p == 0 && a[i] != 0) { count++; } } return count; } // Driver code int main() { int n = 100; cout << composite_factors(n); return 0; } |
Java
// Java implementation of the approach import java.util.*; class Gfg { // Function to return the count // of prime factors of n public static int composite_factors( int n) { int count = 0 ; int i, j; // Initialise array with 0 int [] a= new int [n+ 1 ]; for ( i = 0 ; i < n; i++) { a[i]= 0 ; } for (i = 1 ; i <= n; ++i) { if (n % i == 0 ) { // Stored i value into an array a[i] = i; } } // Every non-zero value at a[i] denotes // that i is a factor of n for (i = 2 ; i <= n; i++) { j = 2 ; int p = 1 ; // Find if i is prime while (j < a[i]) { if (a[i] % j == 0 ) { p = 0 ; break ; } j++; } // If i is a factor of n // and i is not prime if (p == 0 && a[i] != 0 ) { count++; } } return count; } // Driver code public static void main(String[] args) { int n = 100 ; System.out.println(composite_factors(n)); } } // This code is contributed by nidhi16bcs2007 |
Python3
# Python3 implementation of the approach # Function to return the count # of prime factors of n def composite_factors(n) : count = 0 ; # Initialise array with 0 a = [ 0 ] * (n + 1 ) ; for i in range ( 1 , n + 1 ) : if (n % i = = 0 ) : # Stored i value into an array a[i] = i; # Every non-zero value at a[i] denotes # that i is a factor of n for i in range ( 2 ,n + 1 ) : j = 2 ; p = 1 ; # Find if i is prime while (j < a[i]) : if (a[i] % j = = 0 ) : p = 0 ; break ; j + = 1 ; # If i is a factor of n # and i is not prime if (p = = 0 and a[i] ! = 0 ) : count + = 1 ; return count; # Driver code if __name__ = = "__main__" : n = 100 ; print (composite_factors(n)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; class GFG { // Function to return the count // of prime factors of n static int composite_factors( int n) { int count = 0; int i, j; // Initialise array with 0 int [] a = new int [n + 1]; for ( i = 0; i < n; i++) { a[i]=0; } for (i = 1; i <= n; ++i) { if (n % i == 0) { // Stored i value into an array a[i] = i; } } // Every non-zero value at a[i] denotes // that i is a factor of n for (i = 2; i <= n; i++) { j = 2; int p = 1; // Find if i is prime while (j < a[i]) { if (a[i] % j == 0) { p = 0; break ; } j+=1; } // If i is a factor of n // and i is not prime if (p == 0 && a[i] != 0) { count += 1; } } return count; } // Driver code public static void Main() { int n = 100; Console.WriteLine(composite_factors(n)); } } // This code is contributed by mohit kumar 29 |
Javascript
<script> // Javascript implementation of the approach // Function to return the count // of prime factors of n function composite_factors(n) { var count = 0; var i, j; // Initialise array with 0 var a = Array(n + 1).fill(0); for (i = 1; i <= n; ++i) { if (n % i == 0) { // Stored i value into an array a[i] = i; } } // Every non-zero value at a[i] denotes // that i is a factor of n for (i = 2; i <= n; i++) { j = 2; var p = 1; // Find if i is prime while (j < a[i]) { if (a[i] % j == 0) { p = 0; break ; } j++; } // If i is a factor of n // and i is not prime if (p == 0 && a[i] != 0) { count++; } } return count; } // Driver code var n = 100; document.write(composite_factors(n)); </script> |
Output:
6
Time Complexity: O(n*val) where n is the given number and val is the largest factor of n.
Auxiliary Space: O(n)