Find a number that divides maximum array elements | Java program to find a number that divides maximum array elements ; stores smallest prime factor for every number ; Calculating SPF ( Smallest Prime Factor ) for every number till MAXN . Time Complexity : O ( nloglogn ) ; marking smallest prime factor for every number to be itself . ; separately marking spf for every even number as 2 ; checking if i is prime ; marking SPF for all numbers divisible by i ; marking spf [ j ] if it is not previously marked ; A O ( log n ) function returning primefactorization by dividing by smallest prime factor at every step ; Function to find a number that divides maximum array elements ; precalculating Smallest Prime Factor ; Hash to store frequency of each divisors ; Traverse the array and get spf of each element ; calling getFactorization function ; Returns Set view ; Driver program
import java . util . * ; class Solution { static final int MAXN = 100001 ; static int spf [ ] = new int [ MAXN ] ; static void sieve ( ) { spf [ 1 ] = 1 ; for ( int i = 2 ; i < MAXN ; i ++ ) spf [ i ] = i ; for ( int i = 4 ; i < MAXN ; i += 2 ) spf [ i ] = 2 ; for ( int i = 3 ; i * i < MAXN ; i ++ ) { if ( spf [ i ] == i ) { for ( int j = i * i ; j < MAXN ; j += i ) if ( spf [ j ] == j ) spf [ j ] = i ; } } } static Vector < Integer > getFactorization ( int x ) { Vector < Integer > ret = new Vector < Integer > ( ) ; while ( x != 1 ) { int temp = spf [ x ] ; ret . add ( temp ) ; while ( x % temp == 0 ) x = x / temp ; } return ret ; } static int maxElement ( int A [ ] , int n ) { sieve ( ) ; Map < Integer , Integer > m = new HashMap < Integer , Integer > ( ) ; for ( int j = 0 ; j < n ; ++ j ) { Vector < Integer > p = getFactorization ( A [ j ] ) ; for ( int i = 0 ; i < p . size ( ) ; i ++ ) m . put ( p . get ( i ) , m . get ( p . get ( i ) ) == null ? 0 : m . get ( p . get ( i ) ) + 1 ) ; } int cnt = 0 , ans = 10000000 ; Set < Map . Entry < Integer , Integer > > st = m . entrySet ( ) ; for ( Map . Entry < Integer , Integer > me : st ) { if ( me . getValue ( ) >= cnt ) { cnt = me . getValue ( ) ; if ( ans > me . getKey ( ) ) ans = me . getKey ( ) ; else ans = ans ; } } return ans ; } public static void main ( String args [ ] ) { int A [ ] = { 2 , 5 , 10 } ; int n = A . length ; System . out . print ( maxElement ( A , n ) ) ; } }