Count distinct prime factors for each element of an array

0 0 13 minutes read

Given an array arr[] of size N, the task is to find the count of distinct prime factors of each element of the given array.

Examples:

Input: arr[] = {6, 9, 12}
Output: 2 1 2
Explanation:

6 = 2 × 3. Therefore, count = 2

9 = 3 × 3. Therefore, count = 1

12 = 2 × 2 × 3. Therefore, count = 2

The count of distinct prime factors of each array element are 2, 1, 2 respectively.

Input: arr[] = {4, 8, 10, 6}
Output: 1 1 2 2

Naive Approach: The simplest approach to solve the problem is to find the distinct prime factors of each array element. Then, print that count for each array element.

steps to implement-

Run a loop over the given array to find the count of distinct prime factors of each element
For finding the count of distinct prime factors of each element-
- Initialize a variable count with a value of 0
- First, check if the number can be divided by 2. If it can be then divide it by 2 till it can be divided and after that increment the count by 1.
- Then check for all odd numbers from 3 till its square root that it can divide the number or not
- If any odd number can divide then it should divide till it can and after that increment count by 1 for each odd number
- In last, if still we have number>2 then this number that is remaining is any prime number so increment count by 1
- In the last print/return the count

Code-

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// A function to provide count of
//distinct prime factor of a given number
int primeFactors(int n)
{
    //To store count of distinct prime factor of given number
    int count=0;
     
    //Boolean variable to check an element
    //is included in its prime factor or not
    bool val=false;
     
    // Remove all 2s that can be prime factor of n
    while (n % 2 == 0)
    {   
        val=true;
        n = n/2;
    }
     
    //If 2 is included
    if(val==true){count++;}
  
    // n must be odd at this point. So we can skip
    // one element (Note i = i +2)
    for (int i = 3; i <= sqrt(n); i = i + 2)
    {
        //To check whether i is included in prime factor
        val=false;
         
        // While i divides n,divide n
        while (n % i == 0)
        {
            val=true;
            n = n/i;
        }
        //If i is included in prime factor
        if(val==true){count++;}
    }
  
    
    // This condition is to handle the case when n
    // is a prime number greater than 2
    if (n > 2){
       count++; 
    }
      return count; 
}
 
// Function to get the distinct
// factor count of arr[]
void getFactorCount(int arr[],
                    int N)
{
    //Traverse every array element
    for(int i=0;i<N;i++){
        cout<<primeFactors(arr[i])<<" ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 6, 9, 12 };
    int N = sizeof(arr) / sizeof(arr[0]);
    getFactorCount(arr, N);
    return 0;
}

Java

import java.util.*;
 
public class Main {
    // A function to provide count of
    // distinct prime factors of a given number
    static int primeFactors(int n) {
        // To store the count of distinct prime factors of the given number
        int count = 0;
 
        // Boolean variable to check if an element is included in its prime factor or not
        boolean val = false;
 
        // Remove all 2s that can be prime factors of n
        while (n % 2 == 0) {
            val = true;
            n = n / 2;
        }
 
        // If 2 is included
        if (val) {
            count++;
        }
 
        // n must be odd at this point. So we can skip one element (Note i = i + 2)
        for (int i = 3; i <= Math.sqrt(n); i = i + 2) {
            // To check whether i is included in prime factor
            val = false;
 
            // While i divides n, divide n
            while (n % i == 0) {
                val = true;
                n = n / i;
            }
 
            // If i is included in the prime factor
            if (val) {
                count++;
            }
        }
 
        // This condition is to handle the case when n is a prime number greater than 2
        if (n > 2) {
            count++;
        }
 
        return count;
    }
 
    // Function to get the distinct factor count of arr[]
    static void getFactorCount(int[] arr, int N) {
        // Traverse every array element
        for (int i = 0; i < N; i++) {
            System.out.print(primeFactors(arr[i]) + " ");
        }
    }
 
    public static void main(String[] args) {
        int[] arr = { 6, 9, 12 };
        int N = arr.length;
        getFactorCount(arr, N);
    }
}

Python3

import math
 
# A function to provide count of distinct prime factor of a given number
def prime_factors(n):
    # To store count of distinct prime factors of the given number
    count = 0
     
    # Boolean variable to check if an element is included in its prime factors or not
    val = False
     
    # Remove all 2s that can be prime factors of n
    while n % 2 == 0:
        val = True
        n = n // 2
     
    # If 2 is included
    if val == True:
        count += 1
 
    # n must be odd at this point. So we can skip one element (Note i = i + 2)
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        # To check whether i is included in prime factors
        val = False
         
        # While i divides n, divide n
        while n % i == 0:
            val = True
            n = n // i
         
        # If i is included in prime factors
        if val == True:
            count += 1
     
    # This condition is to handle the case when n is a prime number greater than 2
    if n > 2:
        count += 1
 
    return count
 
# Function to get the distinct factor count of arr[]
def get_factor_count(arr):
    # Traverse every array element
    for num in arr:
        print(prime_factors(num), end=" ")
 
# Driver Code
if __name__ == "__main__":
    arr = [6, 9, 12]
    get_factor_count(arr)

Javascript

// JavaScript program for the above approach
 
// A function to provide count of
//distinct prime factor of a given number
function primeFactors(n)
{
    //To store count of distinct prime factor of given number
    let count=0;
     
    //Boolean variable to check an element
    //is included in its prime factor or not
    let val=false;
     
    // Remove all 2s that can be prime factor of n
    while (n % 2 == 0)
    {   
        val=true;
        n = n/2;
    }
     
    //If 2 is included
    if(val==true){count++;}
  
    // n must be odd at this point. So we can skip
    // one element (Note i = i +2)
    for (let i = 3; i <= Math.sqrt(n); i = i + 2)
    {
        //To check whether i is included in prime factor
        val=false;
         
        // While i divides n,divide n
        while (n % i == 0)
        {
            val=true;
            n = n/i;
        }
        //If i is included in prime factor
        if(val==true){count++;}
    }
  
    
    // This condition is to handle the case when n
    // is a prime number greater than 2
    if (n > 2){
       count++; 
    }
      return count; 
}
 
// Function to get the distinct
// factor count of arr[]
function getFactorCount(arr, N)
{
    //Traverse every array element
    for(let i=0;i<N;i++){
        document.write(primeFactors(arr[i])+ " ");
    }
}
 
// Driver Code
    let arr = [ 6, 9, 12 ];
    let N = arr.length;
    getFactorCount(arr, N);

Output-

2 1 2

Time Complexity: O(N * (√Maximum value present in array)), because O(N) in traversing the array and (√Maximum value present in array) is the maximum time to find the count of distinct prime factors of each Number
Auxiliary Space: O(1), because no extra space has been used

Efficient Approach: The above approach can be optimized by precomputing the distinct factors of all the numbers using their Smallest Prime Factors. Follow the steps below to solve the problem

Initialize a vector, say v, to store the distinct prime factors.
Store the Smallest Prime Factor(SPF) up to 10⁵ using a Sieve of Eratosthenes.
Calculate the distinct prime factors of all the numbers by dividing the numbers recursively with their smallest prime factor till it reduces to 1 and store distinct prime factors of X, in v[X].
Traverse the array arr[] and for each array element, print the count as v[arr[i]].size().

Below is the implementation of the above approach :

C++14

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
#define MAX 100001
 
// Stores smallest prime
// factor for every number
int spf[MAX];
 
// Stores distinct prime factors
vector<int> v[MAX];
 
// Function to find the smallest
// prime factor of every number
void sieve()
{
    // Mark the smallest prime factor
    // of every number to itself
    for (int i = 1; i < MAX; i++)
        spf[i] = i;
 
    // Separately mark all the
    // smallest prime factor of
    // every even number to be 2
    for (int i = 4; i < MAX; i = i + 2)
        spf[i] = 2;
 
    for (int i = 3; i * i < MAX; i++)
 
        // If i is prime
        if (spf[i] == i) {
 
            // Mark spf for all numbers
            // divisible by i
            for (int j = i * i; j < MAX;
                 j = j + i) {
 
                // Mark spf[j] if it is
                // not previously marked
                if (spf[j] == j)
                    spf[j] = i;
            }
        }
}
 
// Function to find the distinct
// prime factors
void DistPrime()
{
    for (int i = 1; i < MAX; i++) {
 
        int idx = 1;
        int x = i;
 
        // Push all distinct of x
        // prime factor in v[x]
        if (x != 1)
            v[i].push_back(spf[x]);
 
        x = x / spf[x];
 
        while (x != 1) {
 
            if (v[i][idx - 1]
                != spf[x]) {
 
                // Pushback into v[i]
                v[i].push_back(spf[x]);
 
                // Increment the idx
                idx += 1;
            }
 
            // Update x = (x / spf[x])
            x = x / spf[x];
        }
    }
}
 
// Function to get the distinct
// factor count of arr[]
void getFactorCount(int arr[],
                    int N)
{
    // Precompute the smallest
    // Prime Factors
    sieve();
 
    // For distinct prime factors
    // Fill the v[] vector
    DistPrime();
 
    // Count of Distinct Prime
    // Factors of each array element
    for (int i = 0; i < N; i++) {
        cout << (int)v[arr[i]].size()
             << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 6, 9, 12 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    getFactorCount(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG 
{
 
  static int MAX = 100001;
 
  // Stores smallest prime
  // factor for every number
  static int spf[];
 
  // Stores distinct prime factors
  static ArrayList<Integer> v[];
 
  // Function to find the smallest
  // prime factor of every number
  static void sieve()
  {
 
    // Mark the smallest prime factor
    // of every number to itself
    for (int i = 1; i < MAX; i++)
      spf[i] = i;
 
    // Separately mark all the
    // smallest prime factor of
    // every even number to be 2
    for (int i = 4; i < MAX; i = i + 2)
      spf[i] = 2;
    for (int i = 3; i * i < MAX; i++)
 
      // If i is prime
      if (spf[i] == i) {
 
        // Mark spf for all numbers
        // divisible by i
        for (int j = i * i; j < MAX; j = j + i) {
 
          // Mark spf[j] if it is
          // not previously marked
          if (spf[j] == j)
            spf[j] = i;
        }
      }
  }
 
  // Function to find the distinct
  // prime factors
  static void DistPrime()
  {
    for (int i = 1; i < MAX; i++) {
 
      int idx = 1;
      int x = i;
 
      // Push all distinct of x
      // prime factor in v[x]
      if (x != 1)
        v[i].add(spf[x]);
 
      x = x / spf[x];
 
      while (x != 1) {
 
        if (v[i].get(idx - 1) != spf[x]) {
 
          // Pushback into v[i]
          v[i].add(spf[x]);
 
          // Increment the idx
          idx += 1;
        }
 
        // Update x = (x / spf[x])
        x = x / spf[x];
      }
    }
  }
 
  // Function to get the distinct
  // factor count of arr[]
  static void getFactorCount(int arr[], int N)
  {
 
    // initialization
    spf = new int[MAX];
    v = new ArrayList[MAX];
    for (int i = 0; i < MAX; i++)
      v[i] = new ArrayList<>();
 
    // Precompute the smallest
    // Prime Factors
    sieve();
 
    // For distinct prime factors
    // Fill the v[] vector
    DistPrime();
 
    // Count of Distinct Prime
    // Factors of each array element
    for (int i = 0; i < N; i++) {
      System.out.print((int)v[arr[i]].size() + " ");
    }
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    int arr[] = { 6, 9, 12 };
    int N = arr.length;
 
    getFactorCount(arr, N);
  }
}
 
// This code is contributed by Kingash.

Python3

MAX = 100001
 
# Stores smallest prime
# factor for every number
spf = [0] * MAX
 
# Stores distinct prime factors
v = [[] for _ in range(MAX)]
 
# Function to find the smallest
# prime factor of every number
def sieve():
 
    # Mark the smallest prime factor
    # of every number to itself
    for i in range(1, MAX):
        spf[i] = i
 
    # Separately mark all the
    # smallest prime factor of
    # every even number to be 2
    for i in range(4, MAX, 2):
        spf[i] = 2
    for i in range(3, int(MAX**0.5)+1):
 
        # If i is prime
        if spf[i] == i:
            # Mark spf for all numbers
            # divisible by i
            for j in range(i*i, MAX, i):
                # Mark spf[j] if it is
                # not previously marked
                if spf[j] == j:
                    spf[j] = i
 
# Function to find the distinct
# prime factors
def DistPrime():
    for i in range(1, MAX):
        idx = 1
        x = i
 
        # Push all distinct of x
        # prime factor in v[x]
        if x != 1:
            v[i].append(spf[x])
 
        x = x // spf[x]
 
        while x != 1:
            if v[i][idx-1] != spf[x]:
                # Pushback into v[i]
                v[i].append(spf[x])
 
                # Increment the idx
                idx += 1
 
            # Update x = (x / spf[x])
            x = x // spf[x]
 
# Function to get the distinct
# factor count of arr[]
def getFactorCount(arr, N):
    # Precompute the smallest
    # Prime Factors
    sieve()
 
    # For distinct prime factors
    # Fill the v[] vector
    DistPrime()
 
    # Count of Distinct Prime
    # Factors of each array element
    for i in range(N):
        print(len(v[arr[i]]), end=' ')
 
arr = [6, 9, 12]
N = len(arr)
 
getFactorCount(arr, N)
 
# This code is contributed by phasing17.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG 
{
 
  static int MAX = 100001;
 
  // Stores smallest prime
  // factor for every number
  static int[] spf;
 
  // Stores distinct prime factors
  static List<List<int>> v;
 
  // Function to find the smallest
  // prime factor of every number
  static void sieve()
  {
 
    // Mark the smallest prime factor
    // of every number to itself
    for (int i = 1; i < MAX; i++)
      spf[i] = i;
 
    // Separately mark all the
    // smallest prime factor of
    // every even number to be 2
    for (int i = 4; i < MAX; i = i + 2)
      spf[i] = 2;
    for (int i = 3; i * i < MAX; i++)
 
      // If i is prime
      if (spf[i] == i) {
 
        // Mark spf for all numbers
        // divisible by i
        for (int j = i * i; j < MAX; j = j + i) {
 
          // Mark spf[j] if it is
          // not previously marked
          if (spf[j] == j)
            spf[j] = i;
        }
      }
  }
 
  // Function to find the distinct
  // prime factors
  static void DistPrime()
  {
    for (int i = 1; i < MAX; i++) {
 
      int idx = 1;
      int x = i;
 
      // Push all distinct of x
      // prime factor in v[x]
      if (x != 1)
        v[i].Add(spf[x]);
 
      x = x / spf[x];
 
      while (x != 1) {
 
        if (v[i][idx - 1] != spf[x]) {
 
          // Pushback into v[i]
          v[i].Add(spf[x]);
 
          // Increment the idx
          idx += 1;
        }
 
        // Update x = (x / spf[x])
        x = x / spf[x];
      }
    }
  }
 
  // Function to get the distinct
  // factor count of arr[]
  static void getFactorCount(int[] arr, int N)
  {
 
    // initialization
    spf = new int[MAX];
    v = new List<List<int>>() ;
    for (int i = 0; i < MAX; i++)
      v.Add(new List<int>());
 
    // Precompute the smallest
    // Prime Factors
    sieve();
 
    // For distinct prime factors
    // Fill the v[] vector
    DistPrime();
 
    // Count of Distinct Prime
    // Factors of each array element
    for (int i = 0; i < N; i++) {
      Console.Write((int)v[arr[i]].Count + " ");
    }
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
 
    int[] arr = { 6, 9, 12 };
    int N = arr.Length;
 
    getFactorCount(arr, N);
  }
}
 
// This code is contributed by phasing17.

Javascript

<script>
 
    // JavaScript program for the above approach
     
    let MAX = 100001;
  
    // Stores smallest prime
    // factor for every number
    let spf;
 
    // Stores distinct prime factors
    let v;
 
    // Function to find the smallest
    // prime factor of every number
    function sieve()
    {
 
      // Mark the smallest prime factor
      // of every number to itself
      for (let i = 1; i < MAX; i++)
        spf[i] = i;
 
      // Separately mark all the
      // smallest prime factor of
      // every even number to be 2
      for (let i = 4; i < MAX; i = i + 2)
        spf[i] = 2;
      for (let i = 3; i * i < MAX; i++)
 
        // If i is prime
        if (spf[i] == i) {
 
          // Mark spf for all numbers
          // divisible by i
          for (let j = i * i; j < MAX; j = j + i) {
 
            // Mark spf[j] if it is
            // not previously marked
            if (spf[j] == j)
              spf[j] = i;
          }
        }
    }
 
    // Function to find the distinct
    // prime factors
    function DistPrime()
    {
      for (let i = 1; i < MAX; i++) {
 
        let idx = 1;
        let x = i;
 
        // Push all distinct of x
        // prime factor in v[x]
        if (x != 1)
          v[i].push(spf[x]);
 
        x = parseInt(x / spf[x], 10);
 
        while (x != 1) {
 
          if (v[i][idx - 1] != spf[x]) {
 
            // Pushback into v[i]
            v[i].push(spf[x]);
 
            // Increment the idx
            idx += 1;
          }
 
          // Update x = (x / spf[x])
          x = parseInt(x / spf[x], 10);
        }
      }
    }
 
    // Function to get the distinct
    // factor count of arr[]
    function getFactorCount(arr, N)
    {
 
      // initialization
      spf = new Array(MAX);
      v = new Array(MAX);
      for (let i = 0; i < MAX; i++)
        v[i] = [];
 
      // Precompute the smallest
      // Prime Factors
      sieve();
 
      // For distinct prime factors
      // Fill the v[] vector
      DistPrime();
 
      // Count of Distinct Prime
      // Factors of each array element
      for (let i = 0; i < N; i++) {
        document.write(v[arr[i]].length + " ");
      }
    }
     
    let arr = [ 6, 9, 12 ];
    let N = arr.length;
  
    getFactorCount(arr, N);
   
</script>

Output

2 1 2

Time Complexity: O(N * log N)
Auxiliary Space: O(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 zambiatek!