Dado un número N. La tarea es expresar N como la suma de dos Números Abundantes . Si no es posible, imprima -1.
Ejemplos:
Input : N = 24 Output : 12, 12 Input : N = 5 Output : -1
Enfoque : Un enfoque eficiente es almacenar todos los números abundantes en un conjunto. Y para un número dado, N ejecuta un ciclo de 1 an y verifica si i y ni son números abundantes o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to check if number n is expressed
// as sum of two abundant numbers
#include <bits/stdc++.h>
using namespace std;
#define N 100005
// Function to return all abundant numbers
// This function will be helpful for
// multiple queries
set<int> ABUNDANT()
{
// To store abundant numbers
set<int> v;
for (int i = 1; i < N; i++) {
// to store sum of the divisors
// include 1 in the sum
int sum = 1;
for (int j = 2; j * j <= i; j++) {
// if j is proper divisor
if (i % j == 0) {
sum += j;
// if i is not a perfect square
if (i / j != j)
sum += i / j;
}
}
// if sum is greater than i then i is
// a abundant number
if (sum > i)
v.insert(i);
}
return v;
}
// Check if number n is expressed
// as sum of two abundant numbers
void SumOfAbundant(int n)
{
set<int> v = ABUNDANT();
for (int i = 1; i <= n; i++) {
// if both i and n-i are
// abundant numbers
if (v.count(i) and v.count(n - i)) {
cout << i << " " << n - i;
return;
}
}
// can not be expressed
cout << -1;
}
// Driver code
int main()
{
int n = 24;
SumOfAbundant(n);
return 0;
}
Java
// Java program to check if number n is expressed
// as sum of two abundant numbers
import java.util.*;
class GFG {
static final int N = 100005;
// Function to return all abundant numbers
// This function will be helpful for
// multiple queries
static Set<Integer> ABUNDANT() {
// To store abundant numbers
Set<Integer> v = new HashSet<>();
for (int i = 1; i < N; i++) {
// to store sum of the divisors
// include 1 in the sum
int sum = 1;
for (int j = 2; j * j <= i; j++) {
// if j is proper divisor
if (i % j == 0) {
sum += j;
// if i is not a perfect square
if (i / j != j) {
sum += i / j;
}
}
}
// if sum is greater than i then i is
// a abundant number
if (sum > i) {
v.add(i);
}
}
return v;
}
// Check if number n is expressed
// as sum of two abundant numbers
static void SumOfAbundant(int n) {
Set<Integer> v = ABUNDANT();
for (int i = 1; i <= n; i++) {
// if both i and n-i are
// abundant numbers
if (v.contains(i) & v.contains(n - i)) {
System.out.print(i + " " + (n - i));
return;
}
}
// can not be expressed
System.out.print(-1);
}
// Driver code
public static void main(String[] args) {
int n = 24;
SumOfAbundant(n);
}
}
// This code is contributed by 29AjayKumar
Python 3
# Python 3 program to check if number n is # expressed as sum of two abundant numbers # from math lib import sqrt function from math import sqrt N = 100005 # Function to return all abundant numbers # This function will be helpful for # multiple queries def ABUNDANT() : # To store abundant numbers v = set() ; for i in range(1, N) : # to store sum of the divisors # include 1 in the sum sum = 1 for j in range(2, int(sqrt(i)) + 1) : # if j is proper divisor if (i % j == 0) : sum += j # if i is not a perfect square if (i / j != j) : sum += i // j # if sum is greater than i then i # is a abundant numbe if (sum > i) : v.add(i) return v # Check if number n is expressed # as sum of two abundant numbers def SumOfAbundant(n) : v = ABUNDANT() for i in range(1, n + 1) : # if both i and n-i are abundant numbers if (list(v).count(i) and list(v).count(n - i)) : print(i, " ", n - i) return # can not be expressed print(-1) # Driver code if __name__ == "__main__" : n = 24 SumOfAbundant(n) # This code is contributed by Ryuga
C#
// C# program to check if number n is expressed
// as sum of two abundant numbers
using System;
using System.Collections.Generic;
class GFG {
static readonly int N = 100005;
// Function to return all abundant numbers
// This function will be helpful for
// multiple queries
static HashSet<int> ABUNDANT()
{
// To store abundant numbers
HashSet<int> v = new HashSet<int>();
for (int i = 1; i < N; i++)
{
// to store sum of the divisors
// include 1 in the sum
int sum = 1;
for (int j = 2; j * j <= i; j++)
{
// if j is proper divisor
if (i % j == 0)
{
sum += j;
// if i is not a perfect square
if (i / j != j)
{
sum += i / j;
}
}
}
// if sum is greater than i then i is
// a abundant number
if (sum > i)
{
v.Add(i);
}
}
return v;
}
// Check if number n is expressed
// as sum of two abundant numbers
static void SumOfAbundant(int n)
{
HashSet<int> v = ABUNDANT();
for (int i = 1; i <= n; i++)
{
// if both i and n-i are
// abundant numbers
if (v.Contains(i) & v.Contains(n - i))
{
Console.Write(i + " " + (n - i));
return;
}
}
// can not be expressed
Console.Write(-1);
}
// Driver code
public static void Main()
{
int n = 24;
SumOfAbundant(n);
}
}
// This code is contributed by PrinciRaj1992
PHP
<?php
// PHP program to check if number n is
// expressed as sum of two abundant numbers
// Function to return all abundant numbers
// This function will be helpful for
// multiple queries
function ABUNDANT()
{
$N = 100005;
// To store abundant numbers
$v = array();
for ($i = 1; $i < $N; $i++)
{
// to store sum of the divisors
// include 1 in the sum
$sum = 1;
for ($j = 2; $j * $j <= $i; $j++)
{
// if j is proper divisor
if ($i % $j == 0)
{
$sum += $j;
// if i is not a perfect square
if ($i / $j != $j)
$sum += $i / $j;
}
}
// if sum is greater than i then
// i is a abundant number
if ($sum > $i)
array_push($v, $i);
}
$v = array_unique($v);
return $v;
}
// Check if number n is expressed
// as sum of two abundant numbers
function SumOfAbundant($n)
{
$v = ABUNDANT();
for ($i = 1; $i <= $n; $i++)
{
// if both i and n-i are
// abundant numbers
if (in_array($i, $v) &&
in_array($n - $i, $v))
{
echo $i, " ", $n - $i;
return;
}
}
// can not be expressed
echo -1;
}
// Driver code
$n = 24;
SumOfAbundant($n);
// This code is contributed
// by Arnab Kundu
?>
Javascript
<script>
// javascript program to check if number n is expressed
// as sum of two abundant numbers
var N = 100005;
// Function to return all abundant numbers
// This function will be helpful for
// multiple queries
function ABUNDANT()
{
// To store abundant numbers
var v = new Set();
var i,j;
for (i = 1; i < N; i++) {
// to store sum of the divisors
// include 1 in the sum
var sum = 1;
for (j = 2; j * j <= i; j++) {
// if j is proper divisor
if (i % j == 0) {
sum += j;
// if i is not a perfect square
if (parseInt(i / j) != j)
sum += parseInt(i / j);
}
}
// if sum is greater than i then i is
// a abundant number
if (sum > i)
v.add(i);
}
return v;
}
// Check if number n is expressed
// as sum of two abundant numbers
function SumOfAbundant(n)
{
var v = new Set();
v = ABUNDANT();
var i;
for (i = 1; i <= n; i++) {
// if both i and n-i are
// abundant numbers
if (v.has(i) && v.has(n - i)) {
document.write(i+ ' ' + (n-i))
return;
}
}
// can not be expressed
document.write(-1);
}
// Driver code
var n = 24;
SumOfAbundant(n);
</script>
Producción:
12 12
Complejidad de tiempo: O(n 2 *logn)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA