Sum of element whose prime factors are present in array | Java program to find the sum of the elements of an array whose prime factors are present in the same array ; Stores smallest prime factor for every number ; Function to calculate SPF ( Smallest Prime Factor ) for every number till MAXN ; Marking smallest prime factor for every number to be itself . ; Separately marking spf for every even number as 2 ; If i is prime ; Marking SPF for all numbers divisible by i ; Marking spf [ j ] if it is not previously marked ; Function to return the sum of the elements of an array whose prime factors are present in the same array ; Function call to calculate smallest prime factors of all the numbers upto MAXN ; Create map for each element ; If smallest prime factor of num is present in array ; Each factor of arr [ i ] is present in the array ; Driver program ; Function call to print required answer
import java . util . * ; public class GFG { final static int MAXN = 1000001 ; 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 int sumFactors ( int arr [ ] , int n ) { sieve ( ) ; Map map = new HashMap ( ) ; for ( int i = 0 ; i < MAXN ; ++ i ) map . put ( i , 0 ) ; for ( int i = 0 ; i < n ; ++ i ) map . put ( arr [ i ] , 1 ) ; int sum = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int num = arr [ i ] ; while ( num != 1 && ( int ) ( map . get ( spf [ num ] ) ) == 1 ) { num /= spf [ num ] ; } if ( num == 1 ) sum += arr [ i ] ; } return sum ; } public static void main ( String [ ] args ) { int arr [ ] = { 5 , 11 , 55 , 25 , 100 } ; int n = arr . length ; System . out . println ( sumFactors ( arr , n ) ) ; } }