Given a number N. FInd the sum of he all amicable numbers up to N. If A and B are Amicable pairs (Two numbers are amicable if the first is equal to the sum of divisors of the second) then A and B are called as Amicable numbers.
Examples:
Input : 284
Output : 504
Explanation : 220 and 284 are two amicable numbers upto 284
Input : 250
Output : 220
Explanation : 220 is the only amicable number
Approach :
An efficient approach is to store all amicable numbers in a set and for a given N sum all the numbers in the set which are less than equals to N.
Below code is the implementation of the above approach:
C++
// CPP program to find sum of all// amicable numbers up to n#include <bits/stdc++.h>using namespace std;#define N 100005// Function to return all amicable numbersset<int> AMICABLE(){ int sum[N]; memset(sum, 0, sizeof sum); for (int i = 1; i < N; i++) { // include 1 sum[i]++; for (int j = 2; j * j <= i; j++) { // j is proper divisor of i if (i % j == 0) { sum[i] += j; // if i is not a perfect square if (i / j != j) sum[i] += i / j; } } } set<int> s; for (int i = 2; i < N; i++) { // insert amicable numbers if (i != sum[i] and sum[i] < N and i == sum[sum[i]] and !s.count(i) and !s.count(sum[i])) { s.insert(i); s.insert(sum[i]); } } return s;}// function to find sum of all// amicable numbers up to Nint SumOfAmicable(int n){ // to store required sum int sum = 0; // to store all amicable numbers set<int> s = AMICABLE(); // sum all amicable numbers upto N for (auto i = s.begin(); i != s.end(); ++i) { if (*i <= n) sum += *i; else break; } // required answer return sum;}// Driver code to test above functionsint main(){ int n = 284; cout << SumOfAmicable(n); return 0;} |
Java
// Java program to find sum of all// amicable numbers up to nimport java.util.*;class GFG{ static final int N=100005;// Function to return all amicable numbersstatic Set<Integer> AMICABLE(){ int sum[] = new int[N]; for(int i = 0; i < N; i++) sum[i]=0; for (int i = 1; i < N; i++) { // include 1 sum[i]++; for (int j = 2; j * j <= i; j++) { // j is proper divisor of i if (i % j == 0) { sum[i] += j; // if i is not a perfect square if (i / j != j) sum[i] += i / j; } } } Set<Integer> s = new HashSet<Integer>(); for (int i = 2; i < N; i++) { // insert amicable numbers if (i != sum[i] && sum[i] < N && i == sum[sum[i]]) { s.add(i); s.add(sum[i]); } } return s;}// function to find sum of all// amicable numbers up to Nstatic int SumOfAmicable(int n){ // to store required sum int sum = 0; // to store all amicable numbers Set<Integer> s = AMICABLE(); // sum all amicable numbers upto N for (Integer x : s) { if (x <= n) sum += x; } // required answer return sum;}// Driver code public static void main(String args[]){ int n = 284; System.out.println( SumOfAmicable(n));}}// This code is contributed by Arnab Kundu |
Python3
# Python3 program to findSum of all# amicable numbers up to nimport math as mtN = 100005# Function to return all amicable numbersdef AMICABLE(): Sum = [0 for i in range(N)] for i in range(1, N): Sum[i] += 1 for j in range(2, mt.ceil(mt.sqrt(i))): # j is proper divisor of i if (i % j == 0): Sum[i] += j # if i is not a perfect square if (i // j != j): Sum[i] += i // j s = set() for i in range(2, N): if(i != Sum[i] and Sum[i] < N and i == Sum[Sum[i]] and i not in s and Sum[i] not in s): s.add(i) s.add(Sum[i]) return s# function to findSum of all amicable # numbers up to Ndef SumOfAmicable(n): # to store requiredSum Sum = 0 # to store all amicable numbers s = AMICABLE() #Sum all amicable numbers upto N s = sorted(s) for i in s: if (i <= n): Sum += i else: break # required answer return Sum# Driver Coden = 284print(SumOfAmicable(n))# This code is contributed by # mohit kumar 29 |
C#
// C# program to find sum of all// amicable numbers up to nusing System;using System.Collections.Generic;class GFG{ static readonly int N = 100005;// Function to return all amicable numbersstatic HashSet<int> AMICABLE(){ int []sum = new int[N]; for(int i = 0; i < N; i++) sum[i] = 0; for (int i = 1; i < N; i++) { // include 1 sum[i]++; for (int j = 2; j * j <= i; j++) { // j is proper divisor of i if (i % j == 0) { sum[i] += j; // if i is not a perfect square if (i / j != j) sum[i] += i / j; } } } HashSet<int> s = new HashSet<int>(); for (int i = 2; i < N; i++) { // insert amicable numbers if (i != sum[i] && sum[i] < N && i == sum[sum[i]]) { s.Add(i); s.Add(sum[i]); } } return s;}// function to find sum of all// amicable numbers up to Nstatic int SumOfAmicable(int n){ // to store required sum int sum = 0; // to store all amicable numbers HashSet<int> s = AMICABLE(); // sum all amicable numbers upto N foreach (int x in s) { if (x <= n) sum += x; } // required answer return sum;}// Driver code public static void Main(){ int n = 284; Console.WriteLine( SumOfAmicable(n));}}/* This code contributed by PrinciRaj1992 */ |
PHP
<?php// PHP program to find sum of all// amicable numbers up to n$N = 10005;// Function to return all amicable// numbersfunction AMICABLE(){ global $N; $sum = array_fill(0, $N, 0); for ($i = 1; $i < $N; $i++) { // include 1 $sum[$i]++; for ($j = 2; $j * $j <= $i; $j++) { // j is proper divisor of i if ($i % $j == 0) { $sum[$i] += $j; // if i is not a perfect square if ($i / $j != $j) $sum[$i] += $i / $j; } } } $s = array(); for ($i = 2; $i < $N; $i++) { // insert amicable numbers if ($i != $sum[$i] and $sum[$i] < $N and $i == $sum[$sum[$i]] and !in_array($i, $s) and !in_array($sum[$i], $s)) { array_push($s, $i); array_push($s, $sum[$i]); } } return $s;}// function to find sum of all// amicable numbers up to Nfunction SumOfAmicable($n){ // to store required sum $sum = 0; // to store all amicable numbers $s = AMICABLE(); $s = array_unique($s); sort($s); // sum all amicable numbers upto N for ($i = 0; $i != count($s); ++$i) { if ($s[$i] <= $n) $sum += $s[$i]; else break; } // required answer return $sum;}// Driver code$n = 284;echo SumOfAmicable($n);// This code is contributed by mits?> |
Javascript
<script>// JavaScript program to find sum of all// amicable numbers up to nlet N=100005;// Function to return all amicable numbersfunction AMICABLE(){ let sum = new Array(N); for(let i = 0; i < N; i++) sum[i]=0; for (let i = 1; i < N; i++) { // include 1 sum[i]++; for (let j = 2; j * j <= i; j++) { // j is proper divisor of i if (i % j == 0) { sum[i] += j; // if i is not a perfect square if (i / j != j) sum[i] += i / j; } } } let s = new Set(); for (let i = 2; i < N; i++) { // insert amicable numbers if (i != sum[i] && sum[i] < N && i == sum[sum[i]]) { s.add(i); s.add(sum[i]); } } return s;}// function to find sum of all// amicable numbers up to Nfunction SumOfAmicable(n){ // to store required sum let sum = 0; // to store all amicable numbers let s = AMICABLE(); // sum all amicable numbers upto N for (let x of s.values()) { if (x <= n) sum += x; } // required answer return sum;}// Driver code let n = 284;document.write( SumOfAmicable(n));// This code is contributed by unknown2108</script> |
Output:
504
Time Complexity: O(n2)
Auxiliary Space: O(100005)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
