Dado un entero positivo N, la tarea es verificar si es un número de Proth. Si el número dado es un número de Proth, escriba ‘SÍ’; de lo contrario, escriba ‘NO’.
Número de Proth : en matemáticas, un número de Proth es un número entero positivo de la forma
norte = k * 2 norte + 1
donde k es un entero positivo impar y n es un entero positivo tal que 2 n > k .
Los primeros números de Proth son:
3, 5, 9, 13, 17, 25, 33, 41, 49, ……
Ejemplos:
Input: 25
Output: YES
Taking k= 3 and n= 3,
25 can be expressed in the form of
(k.2n + 1) as (3.23 + 1)
Input: 73
Output: NO
Taking k=9 and n=3
73 can be expressed in the form of
(k.2n + 1 ) as (9.23 + 1)
But 23 is less than 9
(it should be greater than k to be Proth Number)
Acercarse:
- Resta 1 del número. Esto daría un número en la forma k*2 n , si el número dado es un número proth.
- Ahora, recorra todos los números impares desde k=1 hasta n/k y verifique si k puede dividir n de tal manera que (n/k) sea una potencia de 2 o no.
- Si lo encuentra, escriba ‘SÍ’
- Si no se encuentra tal valor de k, imprima ‘NO’
A continuación se muestra la implementación de la idea anterior.
C++
// CPP program to check Proth number
#include <bits/stdc++.h>
using namespace std;
// Utility function to check power of two
bool isPowerOfTwo(int n)
{
return (n && !(n & (n - 1)));
}
// Function to check if the
// Given number is Proth number or not
bool isProthNumber(int n)
{
int k = 1;
while (k < (n / k)) {
// check if k divides n or not
if (n % k == 0) {
// Check if n/k is power of 2 or not
if (isPowerOfTwo(n / k))
return true;
}
// update k to next odd number
k = k + 2;
}
// If we reach here means
// there exists no value of K
// Such that k is odd number
// and n/k is a power of 2 greater than k
return false;
}
// Driver code
int main()
{
// Get n
int n = 25;
// Check n for Proth Number
if (isProthNumber(n - 1))
cout << "YES";
else
cout << "NO";
return 0;
}
Java
// Java program to check for Proth number
class GFG {
// Utility function to check power of two
static boolean isPowerOfTwo(int n)
{
return n != 0 && ((n & (n - 1)) == 0);
}
// Function to check if the
// Given number is Proth number or not
static boolean isProthNumber(int n)
{
int k = 1;
while (k < (n / k)) {
// check if k divides n or not
if (n % k == 0) {
// Check if n/k is power of 2 or not
if (isPowerOfTwo(n / k))
return true;
}
// update k to next odd number
k = k + 2;
}
// If we reach here means
// there exists no value of K
// Such that k is odd number
// and n/k is a power of 2 greater than k
return false;
}
// Driver code
public static void main(String[] args)
{
// Get n
int n = 25;
// Check n for Proth Number
if (isProthNumber(n - 1))
System.out.println("YES");
else
System.out.println("NO");
}
}
Python3
# Python3 program to check for Proth number
# Utility function to Check
# power of two
def isPowerOfTwo(n):
return (n and (not(n & (n - 1))))
# Function to check if the
# Given number is Proth number or not
def isProthNumber( n):
k = 1
while(k < (n//k)):
# check if k divides n or not
if(n % k == 0):
# Check if n / k is power of 2 or not
if(isPowerOfTwo(n//k)):
return True
# update k to next odd number
k = k + 2
# If we reach here means
# there exists no value of K
# Such that k is odd number
# and n / k is a power of 2 greater than k
return False
# Driver code
# Get n
int n = 25;
# Check n for Proth Number
if(isProthNumber(n-1)):
print("YES");
else:
print("NO");
C#
// C# program to check Proth number
using System;
class GFG {
// Utility function to check power of two
static bool isPowerOfTwo(int n)
{
return n != 0 && ((n & (n - 1)) == 0);
}
// Function to check if the
// Given number is Proth number or not
static bool isProthNumber(int n)
{
int k = 1;
while (k < (n / k)) {
// check if k divides n or not
if (n % k == 0) {
// Check if n/k is power of 2 or not
if (isPowerOfTwo(n / k))
return true;
}
// update k to next odd number
k = k + 2;
}
// If we reach here means
// there exists no value of K
// Such that k is odd number
// and n/k is a power of 2 greater than k
return false;
}
// Driver code
public static void Main()
{
// Get n
int n = 25;
// Check n for Proth Number
if (isProthNumber(n - 1))
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
PHP
<?php
// PHP program to check Proth number
// Utility function to check
// power of two
function isPowerOfTwo($n)
{
return ($n && !($n & ($n - 1)));
}
// Function to check if the
// Given number is Proth
// number or not
function isProthNumber($n)
{
$k = 1;
while ($k < ($n / $k))
{
// check if k divides n or not
if ($n % $k == 0)
{
// Check if n/k is power
// of 2 or not
if (isPowerOfTwo($n / $k))
return true;
}
// update k to next odd number
$k = $k + 2;
}
// If we reach here means
// there exists no value of K
// Such that k is odd number
// and n/k is a power of 2
// greater than k
return false;
}
// Driver code
// Get n
$n = 25;
// Check n for Proth Number
if (isProthNumber($n - 1))
echo "YES";
else
echo "NO";
// This code is contributed
// by inder_verma
?>
Javascript
<script>
// Javascript program to check Proth number
// Utility function to check power of two
function isPowerOfTwo(n)
{
return (n && !(n & (n - 1)));
}
// Function to check if the
// Given number is Proth number or not
function isProthNumber(n)
{
let k = 1;
while (k < parseInt(n / k))
{
// Check if k divides n or not
if (n % k == 0)
{
// Check if n/k is power of 2 or not
if (isPowerOfTwo(parseInt(n / k)))
return true;
}
// Update k to next odd number
k = k + 2;
}
// If we reach here means
// there exists no value of K
// Such that k is odd number
// and n/k is a power of 2 greater than k
return false;
}
// Driver code
// Get n
let n = 25;
// Check n for Proth Number
if (isProthNumber(n - 1))
document.write("YES");
else
document.write("NO");
// This code is contributed by souravmahato348
</script>
Producción
YES
Complejidad de tiempo: O(sqrt(n))
Espacio auxiliar: O(1)