Queries to count Composite Magic Numbers from a given range [ L , R ] | C ++ program to implement the above approach ; 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
#include <iostream> NEW_LINE using namespace std ; bool isMagic ( int num ) { return ( num % 9 == 1 ) ; } bool isComposite ( int n ) { if ( n <= 1 ) return false ; if ( n <= 3 ) return false ; if ( n % 2 == 0 n % 3 == 0 ) return true ; for ( int i = 5 ; i * i <= n ; i = i + 6 ) if ( n % i == 0 || n % ( i + 2 ) == 0 ) return true ; return false ; } void find ( int L [ ] , int R [ ] , int q ) { int dp [ 1000005 ] ; dp [ 0 ] = 0 ; dp [ 1 ] = 0 ; for ( int i = 1 ; i < 1000005 ; i ++ ) { if ( isComposite ( i ) && isMagic ( i ) ) { dp [ i ] = dp [ i - 1 ] + 1 ; } else dp [ i ] = dp [ i - 1 ] ; } for ( int i = 0 ; i < q ; i ++ ) cout << dp [ R [ i ] ] - dp [ L [ i ] - 1 ] << endl ; } int main ( ) { int L [ ] = { 10 , 3 } ; int R [ ] = { 100 , 2279 } ; int Q = 2 ; find ( L , R , Q ) ; return 0 ; }