Remove characters from given string whose frequencies are a Prime Number | Function to perform the seive of eratosthenes algorithm ; Initialize all entries in prime [ ] as true ; Initialize 0 and 1 as non prime ; Traversing the prime array ; If i is prime ; All multiples of i must be marked false as they are non prime ; Function to remove characters which have prime frequency in the String ; Length of the String ; Create a bool array prime ; Sieve of Eratosthenes ; Stores the frequency of character ; Storing the frequencies ; New String that will be formed ; Removing the characters which have prime frequencies ; If the character has prime frequency then skip ; Else concatenate the character to the new String ; Print the modified String ; Driver Code ; Function Call
def SieveOfEratosthenes ( prime , n ) : NEW_LINE INDENT for i in range ( n + 1 ) : NEW_LINE INDENT prime [ i ] = True NEW_LINE DEDENT prime [ 0 ] = prime [ 1 ] = False NEW_LINE i = 2 NEW_LINE while i * i <= n : NEW_LINE INDENT if ( prime [ i ] == True ) : NEW_LINE INDENT j = 2 NEW_LINE while i * j <= n : NEW_LINE INDENT prime [ i * j ] = False NEW_LINE j += 1 NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT DEDENT def removePrimeFrequencies ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE prime = [ False ] * ( n + 1 ) NEW_LINE SieveOfEratosthenes ( prime , n ) NEW_LINE m = { } NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT if s [ i ] in m : NEW_LINE INDENT m [ s [ i ] ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT m [ s [ i ] ] = 1 NEW_LINE DEDENT DEDENT new_String = " " NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT if ( prime [ m [ s [ i ] ] ] ) : NEW_LINE INDENT continue NEW_LINE DEDENT new_String += s [ i ] NEW_LINE DEDENT print ( new_String , end = " " ) NEW_LINE DEDENT Str = " geeksforgeeks " NEW_LINE removePrimeFrequencies ( list ( Str ) ) NEW_LINE