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