Blum Integer | Function to cheek if number is Blum Integer ; to store prime numbers from 2 to n ; If prime [ i ] is not changed , then it is a prime ; Update all multiples of p ; to check if the given odd integer is Blum Integer or not ; checking the factors are of 4 t + 3 form or not ; give odd integer greater than 20
def isBlumInteger ( n ) : NEW_LINE INDENT prime = [ True ] * ( n + 1 ) NEW_LINE i = 2 NEW_LINE while ( i * i <= n ) : NEW_LINE INDENT if ( prime [ i ] == True ) : NEW_LINE INDENT for j in range ( i * 2 , n + 1 , i ) : NEW_LINE INDENT prime [ j ] = False NEW_LINE DEDENT DEDENT i = i + 1 NEW_LINE DEDENT for i in range ( 2 , n + 1 ) : NEW_LINE INDENT if ( prime [ i ] ) : NEW_LINE INDENT if ( ( n % i == 0 ) and ( ( i - 3 ) % 4 ) == 0 ) : NEW_LINE INDENT q = int ( n / i ) NEW_LINE return ( q != i and prime [ q ] and ( q - 3 ) % 4 == 0 ) NEW_LINE DEDENT DEDENT DEDENT return False NEW_LINE DEDENT n = 249 NEW_LINE if ( isBlumInteger ( n ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT