Dado un número N , la tarea es verificar si N es un número intocable o no. Si N es un número intocable , escriba «Sí» , de lo contrario, escriba «No» .
Los números intocables son números que no son la suma de los divisores propios de ningún número.
Ejemplos:
Entrada: N = 5
Salida: Sí
Entrada: N = 20
Salida: No
Planteamiento: La idea es encontrar la suma de los divisores propios del número N y verificar si la suma es igual a N o no. Si la suma no es igual a N , entonces N es un número intocable , luego imprima «Sí» , de lo contrario, imprima «No» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate sum of
// all proper divisors of num
int divSum(int num)
{
// Final result of summation
// of divisors
int result = 0;
// Find all divisors of num
for (int i = 2; i <= sqrt(num); i++) {
// If 'i' is divisor of 'num'
if (num % i == 0) {
// If both divisors are same
// then add it only once else
// add both
if (i == (num / i))
result += i;
else
result += (i + num / i);
}
}
// Add 1 to the result as
// 1 is also a divisor
return (result + 1);
}
// Function to check if N is a
// Untouchable Number
bool isUntouchable(int n)
{
for (int i = 1; i <= 2 * n; i++) {
if (divSum(i) == n)
return false;
}
return true;
}
// Driver Code
int main()
{
// Given Number N
int N = 52;
// Function Call
if (isUntouchable(n))
cout << "Yes";
else
cout << "No";
}
Java
// Java program for the above approach
class GFG{
// Function to calculate sum of
// all proper divisors of num
static int divSum(int num)
{
// Final result of summation
// of divisors
int result = 0;
// Find all divisors of num
for(int i = 2; i <= Math.sqrt(num); i++)
{
// If 'i' is divisor of 'num'
if (num % i == 0)
{
// If both divisors are same
// then add it only once else
// add both
if (i == (num / i))
result += i;
else
result += (i + num / i);
}
}
// Add 1 to the result as
// 1 is also a divisor
return (result + 1);
}
// Function to check if N is a
// Untouchable Number
static boolean isUntouchable(int n)
{
for(int i = 1; i <= 2 * n; i++)
{
if (divSum(i) == n)
return false;
}
return true;
}
// Driver code
public static void main(String[] args)
{
// Given Number N
int n = 52;
// Function Call
if (isUntouchable(n))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Pratima Pandey
Python3
# Python3 program for the above approach
import math;
# Function to calculate sum of
# all proper divisors of num
def divSum(num):
# Final result of summation
# of divisors
result = 0;
# Find all divisors of num
for i in range(2, int(math.sqrt(num))):
# If 'i' is divisor of 'num'
if (num % i == 0):
# If both divisors are same
# then add it only once else
# add both
if (i == (num // i)):
result += i;
else:
result += (i + num // i);
# Add 1 to the result as
# 1 is also a divisor
return (result + 1);
# Function to check if N is a
# Untouchable Number
def isUntouchable(n):
for i in range(1, 2 * n):
if (divSum(i) == n):
return False;
return True;
# Driver Code
# Given Number N
N = 52;
# Function Call
if (isUntouchable(N)):
print("Yes");
else:
print("No");
# This code is contributed by Code_Mech
C#
// C# program for the above approach
using System;
class GFG{
// Function to calculate sum of
// all proper divisors of num
static int divSum(int num)
{
// Final result of summation
// of divisors
int result = 0;
// Find all divisors of num
for(int i = 2; i <= Math.Sqrt(num); i++)
{
// If 'i' is divisor of 'num'
if (num % i == 0)
{
// If both divisors are same
// then add it only once else
// add both
if (i == (num / i))
result += i;
else
result += (i + num / i);
}
}
// Add 1 to the result as
// 1 is also a divisor
return (result + 1);
}
// Function to check if N is a
// Untouchable Number
static bool isUntouchable(int n)
{
for(int i = 1; i <= 2 * n; i++)
{
if (divSum(i) == n)
return false;
}
return true;
}
// Driver code
public static void Main()
{
// Given Number N
int n = 52;
// Function Call
if (isUntouchable(n))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// JavaScript program for the above approach
// Function to calculate sum of
// all proper divisors of num
function divSum(num)
{
// Final result of summation
// of divisors
let result = 0;
// Find all divisors of num
for (let i = 2; i <= Math.sqrt(num); i++)
{
// If 'i' is divisor of 'num'
if (num % i == 0)
{
// If both divisors are same
// then add it only once else
// add both
if (i == (num / i))
result += i;
else
result += (i + num / i);
}
}
// Add 1 to the result as
// 1 is also a divisor
return (result + 1);
}
// Function to check if N is a
// Untouchable Number
function isUntouchable(n)
{
for (let i = 1; i <= 2 * n; i++)
{
if (divSum(i) == n)
return false;
}
return true;
}
// Driver Code
// Given Number n
let n = 52;
// Function Call
if (isUntouchable(n))
document.write("Yes");
else
document.write("No");
// This code is contributed by blalverma92
</script>
Producción:
Yes
Complejidad del tiempo: O(sqrt(N))