Last Updated : 02 Nov, 2023
Summarize
Comments
Improve
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)
C#
using
System;
class
Program
{
// A function to provide the 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 factors or not
bool
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 += 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)
{
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 an array
static
void
GetFactorCount(
int
[] arr)
{
// Traverse every array element
foreach
(
int
num
in
arr)
{
Console.Write(PrimeFactors(num) +
" "
);
}
}
static
void
Main()
{
int
[] arr = { 6, 9, 12 };
GetFactorCount(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 105 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)
Next Article
Maximize sum of count of distinct prime factors of K array elements