Queries to count Composite Magic Numbers from a given range [ L , R ] | Check if a number is magic number or not ; Check number is composite number or not ; Corner cases ; Check if the number is a multiple of 2 or 3 ; Check for multiples of remaining primes ; Function to find Composite Magic Numbers in given ranges ; dp [ i ] : Stores the count of composite Magic numbers up to i ; Traverse in the range [ 1 , 1e5 ) ; Check if number is Composite number as well as a Magic number or not ; Print results for each query ; Driver Code
def isMagic ( num ) : NEW_LINE INDENT return ( num % 9 == 1 ) NEW_LINE DEDENT def isComposite ( n ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( n <= 3 ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( n % 2 == 0 or n % 3 == 0 ) : NEW_LINE INDENT return True NEW_LINE DEDENT for i in range ( 5 , n + 1 , 6 ) : NEW_LINE INDENT if i * i > n + 1 : NEW_LINE INDENT break NEW_LINE DEDENT if ( n % i == 0 or n % ( i + 2 ) == 0 ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT def find ( L , R , q ) : NEW_LINE INDENT dp = [ 0 ] * 1000005 NEW_LINE dp [ 0 ] = 0 NEW_LINE dp [ 1 ] = 0 NEW_LINE for i in range ( 1 , 1000005 ) : NEW_LINE INDENT if ( isComposite ( i ) and isMagic ( i ) ) : NEW_LINE INDENT dp [ i ] = dp [ i - 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] = dp [ i - 1 ] NEW_LINE DEDENT DEDENT for i in range ( q ) : NEW_LINE INDENT print ( dp [ R [ i ] ] - dp [ L [ i ] - 1 ] ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT L = [ 10 , 3 ] NEW_LINE R = [ 100 , 2279 ] NEW_LINE Q = 2 NEW_LINE find ( L , R , Q ) NEW_LINE DEDENT