Find prime number K in an array such that ( A [ i ] % K ) is maximum | Python 3 implementation of the approach ; Function to return the required prime number from the array ; Find maximum value in the array ; USE SIEVE TO FIND ALL PRIME NUMBERS LESS THAN OR EQUAL TO max_val Create a boolean array " prime [ 0 . . n ] " . A value in prime [ i ] will finally be false if i is Not a prime , else true . ; Remaining part of SIEVE ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p ; To store the maximum prime number ; If current element is prime then update the maximum prime ; Return the maximum prime number from the array ; Driver code
from math import sqrt NEW_LINE def getPrime ( arr , n ) : NEW_LINE INDENT max_val = arr [ 0 ] NEW_LINE for i in range ( len ( arr ) ) : NEW_LINE INDENT if ( arr [ i ] > max_val ) : NEW_LINE INDENT max_val = arr [ i ] NEW_LINE DEDENT DEDENT prime = [ True for i in range ( max_val + 1 ) ] NEW_LINE prime [ 0 ] = False NEW_LINE prime [ 1 ] = False NEW_LINE for p in range ( 2 , int ( sqrt ( max_val ) ) + 1 , 1 ) : NEW_LINE INDENT if ( prime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * 2 , max_val + 1 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT DEDENT maximum = - 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( prime [ arr [ i ] ] ) : NEW_LINE INDENT maximum = max ( maximum , arr [ i ] ) NEW_LINE DEDENT DEDENT return maximum NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 10 , 15 , 7 , 6 , 8 , 13 ] NEW_LINE n = len ( arr ) NEW_LINE print ( getPrime ( arr , n ) ) NEW_LINE DEDENT