Encuentra elementos en un rango dado que tengan al menos un divisor impar

Dados dos números enteros N y M , la tarea es imprimir todos los elementos en el rango [N, M] que tengan al menos un divisor impar.
Ejemplos: 
 

Entrada: N = 2, M = 10 
Salida: 3 5 6 7 9 10 
Explicación: 
3, 6 tienen un divisor impar 3 
5, 10 tienen un divisor impar 5 
7 tienen un divisor impar 7 
9 tienen dos divisores impares 3, 9
Entrada : N = 15, M = 20 
Salida: 15 17 18 19 20 
 

Enfoque ingenuo: 
el enfoque más simple es recorrer todos los números en el rango [1, N] y, para cada elemento, verificar si tiene un divisor impar o no. 
Complejidad de tiempo: O(N ^3/2 )
Enfoque eficiente: 
Para optimizar el enfoque anterior, debemos observar los siguientes detalles: 
 

• Cualquier número que sea potencia de 2 no tiene divisores impares.
• Todos los demás elementos tendrán al menos un divisor impar

Ilustración: 
En el rango [3, 10], los elementos que tienen al menos un divisor impar son {3, 5, 6, 7, 9, 10} y {4, 8} no contiene ningún divisor impar. 
 

Siga los pasos a continuación para resolver el problema: 
 

• Recorra el rango [N, M] y verifique para cada elemento si alguno de sus bits establecidos está establecido en el número anterior o no, es decir, verifique si i & (i – 1) es igual a 0 o no. 
   
• Si es así, entonces el número es una potencia de 2 y no se considera. De lo contrario, imprima el número ya que no es una potencia de 2 y tiene al menos un divisor impar. 
   

A continuación se muestra la implementación del enfoque anterior.
 

// C++ program to print all numbers
// with least one odd factor in the
// given range
#include <bits/stdc++.h>
using namespace std;
 
// Function to prints all numbers
// with at least one odd divisor
int printOddFactorNumber(int n,
                         int m)
{
    for (int i = n; i <= m; i++) {
 
        // Check if the number is
        // not a power of two
        if ((i > 0)
            && ((i & (i - 1)) != 0))
 
            cout << i << " ";
    }
}
 
// Driver Code
int main()
{
    int N = 2, M = 10;
    printOddFactorNumber(N, M);
    return 0;
}

// Java program to print all numbers
// with least one odd factor in the
// given range
class GFG{
 
// Function to prints all numbers
// with at least one odd divisor
static int printOddFactorNumber(int n,
                                int m)
{
    for (int i = n; i <= m; i++)
    {
 
        // Check if the number is
        // not a power of two
        if ((i > 0) && ((i & (i - 1)) != 0))
 
            System.out.print(i + " ");
    }
    return 0;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 2, M = 10;
    printOddFactorNumber(N, M);
}
}
 
// This code is contributed
// by shivanisinghss2110

# Python3 program to print all numbers
# with least one odd factor in the
# given range
 
# Function to prints all numbers
# with at least one odd divisor
def printOddFactorNumber(n, m):
     
    for i in range(n, m + 1):
 
        # Check if the number is
        # not a power of two
        if ((i > 0) and ((i & (i - 1)) != 0)):
            print(i, end = " ")
             
# Driver Code
N = 2
M = 10
 
printOddFactorNumber(N, M)
 
# This code is contributed by Vishal Maurya

// C# program to print all numbers
// with least one odd factor in the
// given range
using System;
class GFG{
 
// Function to prints all numbers
// with at least one odd divisor
static int printOddFactorNumber(int n,
                                int m)
{
    for (int i = n; i <= m; i++)
    {
 
        // Check if the number is
        // not a power of two
        if ((i > 0) && ((i & (i - 1)) != 0))
 
            Console.Write(i + " ");
    }
    return 0;
}
 
// Driver Code
public static void Main()
{
    int N = 2, M = 10;
    printOddFactorNumber(N, M);
}
}
 
// This code is contributed
// by Code_Mech

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to prints all numbers
// with at least one odd divisor
function printOddFactorNumber(n, m)
{
    for (let i = n; i <= m; i++)
    {
   
        // Check if the number is
        // not a power of two
        if ((i > 0) && ((i & (i - 1)) != 0))
   
            document.write(i + " ");
    }
    return 0;
}
 
// Driver code
    let N = 2, M = 10;
    printOddFactorNumber(N, M);
 
// This code is contributed by susmitakundugoaldanga.
</script>

3 5 6 7 9 10

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)