Comprueba si un número dado N tiene al menos un divisor impar que no exceda N – 1

Dado un entero positivo N , la tarea es verificar si el número dado N tiene al menos 1 divisor impar del rango [2, N – 1] o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .

Ejemplos:

Entrada: N = 10
Salida: Sí
Explicación:
10 tiene 5 como divisor impar. Por lo tanto, imprima Sí.

Entrada: N = 8
Salida: No

Enfoque: La idea para resolver el problema dado es iterar a través de todos los divisores impares posibles en el rango [3, sqrt(N)] y, si existe tal divisor , imprimir «Sí» . De lo contrario, escriba “No” .
 

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether N
// has at least one odd divisor
// not exceeding N - 1 or not
string oddDivisor(int N)
{
    // Stores the value of N
    int X = N;
 
    // Reduce the given number
    // N by dividing it by 2
    while (N % 2 == 0) {
        N /= 2;
    }
 
    for (int i = 3; i * i <= X; i += 2) {
 
        // If N is divisible by
        // an odd divisor i
        if (N % i == 0) {
            return "Yes";
        }
    }
 
    // Check if N is an odd divisor after
    // reducing N by dividing it by 2
    if (N != X)
        return "Yes";
 
    // Otherwise
    return "No";
}
 
// Driver Code
int main()
{
    int N = 10;
 
    // Function Call
    cout << oddDivisor(N);
 
    return 0;
}

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG {
 
    // Function to check whether N
    // has at least one odd divisor
    // not exceeding N - 1 or not
    public static String oddDivisor(int N)
    {
       
        // Stores the value of N
        int X = N;
 
        // Reduce the given number
        // N by dividing it by 2
        while (N % 2 == 0) {
            N /= 2;
        }
 
        for (int i = 3; i * i <= X; i += 2) {
 
            // If N is divisible by
            // an odd divisor i
            if (N % i == 0) {
                return "Yes";
            }
        }
 
        // Check if N is an odd divisor after
        // reducing N by dividing it by 2
        if (N != X) {
            return "Yes";
        }
       
        // Otherwise
        return "No";
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 10;
       
        // Function Call
        System.out.println(oddDivisor(N));
    }
}
 
// This code is contributed by aditya7409.

# Python program for the above approach
 
# Function to check whether N
# has at least one odd divisor
# not exceeding N - 1 or not
def oddDivisor(N):
     
    # Stores the value of N
    X = N
     
    # Reduce the given number
    # N by dividing it by 2
    while (N % 2 == 0):
        N //= 2
     
    i = 3
    while(i * i <= X):
         
        # If N is divisible by
        # an odd divisor i
        if (N % i == 0):
            return "Yes"
        i += 2
     
    # Check if N is an odd divisor after
    # reducing N by dividing it by 2
    if (N != X):
        return "Yes"
     
    # Otherwise
    return "No"
     
# Driver Code
 
N = 10
# Function Call
print(oddDivisor(N))
 
# This code is contributed by shubhamsingh10

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
  // Function to check whether N
  // has at least one odd divisor
  // not exceeding N - 1 or not
  public static string oddDivisor(int N)
  {
 
    // Stores the value of N
    int X = N;
 
    // Reduce the given number
    // N by dividing it by 2
    while (N % 2 == 0) {
      N /= 2;
    }
 
    for (int i = 3; i * i <= X; i += 2) {
 
      // If N is divisible by
      // an odd divisor i
      if (N % i == 0) {
        return "Yes";
      }
    }
 
    // Check if N is an odd divisor after
    // reducing N by dividing it by 2
    if (N != X) {
      return "Yes";
    }
 
    // Otherwise
    return "No";
  }
 
  // Driver Code
  static public void Main()
  {
    int N = 10;
 
    // Function Call
    Console.Write(oddDivisor(N));
  }
}
 
// This code is contributed by sanjoy_62.

<script>
 
// javascript program for the above approach
 
// Function to check whether N
// has at least one odd divisor
// not exceeding N - 1 or not
function oddDivisor(N)
{
 
    // Stores the value of N
    var X = N;
    var i;
     
    // Reduce the given number
    // N by dividing it by 2
    while (N % 2 == 0) {
        N /= 2;
    }
 
    for (i = 3; i * i <= X; i += 2) {
 
        // If N is divisible by
        // an odd divisor i
        if (N % i == 0) {
            return "Yes";
        }
    }
 
    // Check if N is an odd divisor after
    // reducing N by dividing it by 2
    if (N != X)
        return "Yes";
 
    // Otherwise
    return "No";
}
 
// Driver Code
    var N = 10;
 
    // Function Call
    document.write(oddDivisor(N));
 
// This code is contributed by ipg2016107.
</script>

Yes

Complejidad de Tiempo: O(√N)
Espacio Auxiliar: O(1)

Otro enfoque: la única posibilidad de que cualquier número n>1 no tenga un divisor impar es que n sea una potencia de dos.

Para verificar la potencia de dos, podemos usar este enfoque 

n&(n−1) , el resultado será cero solo si n es una potencia de dos.

#include <iostream>
using namespace std;
 
void oddDivisor(int n){
  //checking power of two or not
  if ((n & (n - 1)) == 0) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
}
 
int main() {
    int N = 10;
 
    // Function Call
    oddDivisor(N);
   
    return 0;
}

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
   
    public static void main (String[] args) {
      int N = 10;
 
    // Function Call
    oddDivisor(N);
    }
   
  static void oddDivisor(int n){
  //checking power of two or not
  if ((n & (n - 1)) == 0) {
        System.out.println("NO");
    } else {
        System.out.println("YES");
    }
}
}

YES