FOR FREE MATERIALS
Amicable Numbers
Back to ProgrammingDescription
If there is a pair of a number such that the sum of the factors (excluding the number itself) of first number is equal to the second number and the sum of the factors (excluding the number itself) of the second number is equal to the first number.
For example 220 and 284.
The factors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110. If we add these factors we will get 284 which is equal to the second number and the factors of 284 are 1, 2, 4, 71, and 142, after adding them we get 220 which is equal to the first number. Therefore, this pair is called amicable numbers.
For this program, two numbers are taken as inputs. Then the sum of the factors of each number is calculated. The sum of the factors of the first number is compared with the second number and the sum of the factors of the second number is compared with the first number. If both the conditions satisfy then the pairs are called amicable numbers otherwise not.
Algorithm
INPUT: Two Numbers
OUTPUT: Whether the numbers are amicable numbers or not.
PROCESS:
Step 1: [Taking the inputs]
Read m, n [The two numbers]
Step 2: [Checking for amicable numbers]
Set s1<-0
Set s2<-0
[Adding the factors of the 1st number(m)]
For i=1 to m/2 repeat
[If 'i' is a factor, add it]
If m mod i=0 then
Set s1<-s1+i
[End of ‘if’]
[End of ‘for’ loop]
[Adding the factors of the 2nd number(n)]
For i=1 to n/2 repeat
[If 'i' is a factor, add it]
If n mod i=0 then
Set s2<-s2+i
[End of ‘if’]
[End of ‘for’ loop]
[Checking for amicable number]
If s1=n and s2=m then
Print "The given numbers are amicable numbers"
Else
Print "The given numbers are not amicable number"
[End of ‘if-else’]
Step 3: Stop.
Code
Time Complexity:
for(i=1;i<=m/2;i++)---------------------------------------O(m)
{ //if 'i' is a factor, add it
if(m%i==0)
s1=s1+i; }
//adding the factors of the 2nd number(n)
for(i=1;i<=n/2;i++)-------------------------------------O(n)
{ //if 'i' is a factor, add it
if(n%i==0)
s2=s2+i; }
The time complexity of this program is O(m+n) where ‘m’ and ‘n’ are the two numbers that are to be checked for amicable numbers.
Space Complexity:
The space complexity is O(1) as it requires a fixed number of memory spaces for any given pairs of numbers.
