Sum of element whose prime factors are present in array | Python 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 Code ; Function call to print required answer
from collections import defaultdict NEW_LINE MAXN = 1000001 NEW_LINE MAXN_sqrt = int ( MAXN ** ( 0.5 ) ) NEW_LINE spf = [ None ] * ( MAXN ) NEW_LINE def sieve ( ) : NEW_LINE INDENT spf [ 1 ] = 1 NEW_LINE for i in range ( 2 , MAXN ) : NEW_LINE INDENT spf [ i ] = i NEW_LINE DEDENT for i in range ( 4 , MAXN , 2 ) : NEW_LINE INDENT spf [ i ] = 2 NEW_LINE DEDENT for i in range ( 3 , MAXN_sqrt ) : NEW_LINE INDENT if spf [ i ] == i : NEW_LINE INDENT for j in range ( i * i , MAXN , i ) : NEW_LINE INDENT if spf [ j ] == j : NEW_LINE INDENT spf [ j ] = i NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT def sumFactors ( arr , n ) : NEW_LINE INDENT sieve ( ) NEW_LINE Map = defaultdict ( lambda : 0 ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT Map [ arr [ i ] ] = 1 NEW_LINE DEDENT Sum = 0 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT num = arr [ i ] NEW_LINE while num != 1 and Map [ spf [ num ] ] == 1 : NEW_LINE INDENT num = num // spf [ num ] NEW_LINE DEDENT if num == 1 : NEW_LINE INDENT Sum += arr [ i ] NEW_LINE DEDENT DEDENT return Sum NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 5 , 11 , 55 , 25 , 100 ] NEW_LINE n = len ( arr ) NEW_LINE print ( sumFactors ( arr , n ) ) NEW_LINE DEDENT