Skip to main content

Find the sum of factors of a given number

The problem is to find the sum of all factors of a given positive integer. Factors are numbers that divide the given number without leaving a remainder. The sum of factors includes the number itself and 1, as all numbers are divisible by themselves and 1.

Example: Consider the number 10. Factors of 10: 1, 2, 5, 10 Sum of factors: 1 + 2 + 5 + 10 = 18

Pseudocode

  1. Start with the input number as the result.
  2. Loop from 1 to half of the input number (since factors beyond half will repeat).
  3. Check if the current loop variable divides the input number without leaving a remainder.
  4. If it does, add it to the result.
  5. After the loop, print the factors and the result.

Algorithm

factor_sum(number):
    result = number
    print("Number: ", number)
    print("Factors: [")
    for i from 1 to number/2:
        if number % i == 0:
            print(i, ",")
            result += i
    print(number, "]")
    print("Factors sum: ", result)

Explanation

  1. We initialize a variable result with the value of the input number. This is because any number is always divisible by itself, so we start with its factor sum as the number itself.
  2. We iterate from 1 to number/2 in the for loop to find the factors of the number. Looping only up to number/2 is sufficient because factors beyond half will be duplicates (e.g., for 10, if we check factors beyond 5, we will have already counted them).
  3. Inside the loop, we check if the current value of i is a factor of the input number. If number % i == 0, it means i divides number without leaving a remainder.
  4. If i is a factor, we print it as one of the factors and add its value to the result variable.
  5. After the loop, we print the closing bracket for the factors list and display the result of the sum of factors.

Code Solution

Here given code implementation process.

//C Program
//Find the sum of factors of a given number
#include <stdio.h>

void factor_sum(long long number)
{
	long long result = number;
	printf("Number :  %lld ", number);
	printf("\nFactors : [");
	for (int i = 1; i <= number / 2; ++i)
	{
		//Check whether resultant remainder of number divisible by n  is zero or not
		if (number % i == 0)
		{
			printf("%d,", i);
			//Sum Factors
			result += i;
		}
	}
	//Given number is itself factor
	printf("%lld", number);
	printf("]\n");
	printf("Factors sum : %lld\n\n", result);
}
int main()
{
	//Test Cases
	factor_sum(50);
	factor_sum(180);
	factor_sum(11);
	factor_sum(1);
	return 0;
}

Output

Number :  50
Factors : [1,2,5,10,25,50]
Factors sum : 93

Number :  180
Factors : [1,2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90,180]
Factors sum : 546

Number :  11
Factors : [1,11]
Factors sum : 12

Number :  1
Factors : [1]
Factors sum : 1

/*
  C++ program
  Find the sum of factors of a given number
*/
#include<iostream>

using namespace std;
class MyNumber
{
	public: void factor_sum(long number)
	{
		long result = number;
		cout << "Number : " << number << " ";
		cout << "\nFactors : [";
		for (int i = 1; i <= number / 2; ++i)
		{
			//Check whether resultant remainder of number divisible by n  is zero or not
			if (number % i == 0)
			{
				cout << i << ",";
				//Sum Factors
				result += i;
			}
		}
		cout << number;
		cout << "]\n";
		cout << "Factors sum : " << result << "\n\n";
	}
};
int main()
{
	MyNumber obj =  MyNumber();
	//Test Cases
	obj.factor_sum(50);
	obj.factor_sum(180);
	obj.factor_sum(11);
	obj.factor_sum(1);
	return 0;
}

Output

Number : 50
Factors : [1,2,5,10,25,50]
Factors sum : 93

Number : 180
Factors : [1,2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90,180]
Factors sum : 546

Number : 11
Factors : [1,11]
Factors sum : 12

Number : 1
Factors : [1]
Factors sum : 1

/*
  Java program
  Find the sum of factors of a given number
*/
public class MyNumber
{
	public void factor_sum(long number)
	{
		long result = number;
		System.out.print("Number : " + number + " ");
		System.out.print("\nFactors : [");
		for (int i = 1; i <= number / 2; ++i)
		{
			//Check whether resultant remainder of number divisible by n  is zero or not
			if (number % i == 0)
			{
				System.out.print(i + ",");
				//Sum Factors
				result += i;
			}
		}
		//Given number is itself factor
		System.out.print(number);
		System.out.print("]\n");
		System.out.print("Factors sum : " + result + "\n\n");
	}
	public static void main(String[] args)
	{
		MyNumber obj = new MyNumber();
		//Test Cases
		obj.factor_sum(50);
		obj.factor_sum(180);
		obj.factor_sum(11);
		obj.factor_sum(1);
	}
}

Output

Number : 50
Factors : [1,2,5,10,25,50]
Factors sum : 93

Number : 180
Factors : [1,2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90,180]
Factors sum : 546

Number : 11
Factors : [1,11]
Factors sum : 12

Number : 1
Factors : [1]
Factors sum : 1

/*
  C# program
  Find the sum of factors of a given number
*/
using System;
public class MyNumber
{
	public void factor_sum(long number)
	{
		long result = number;
		Console.Write("Number : " + number + " ");
		Console.Write("\nFactors : [");
		for (int i = 1; i <= number / 2; i++)
		{
			//Check whether resultant reMainder of number divisible by n  is zero or not
			if (number % i == 0)
			{
				Console.Write(i + ",");
				//Sum Factors
				result += i;
			}
		}
		Console.Write(number);
		Console.Write("]\n");
		Console.Write("Factors sum : " + result + "\n\n");
	}
	public static void Main(String[] args)
	{
		MyNumber obj = new MyNumber();
		//Test Cases
		obj.factor_sum(50);
		obj.factor_sum(180);
		obj.factor_sum(11);
		obj.factor_sum(1);
	}
}

Output

Number : 50
Factors : [1,2,5,10,25,50]
Factors sum : 93

Number : 180
Factors : [1,2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90,180]
Factors sum : 546

Number : 11
Factors : [1,11]
Factors sum : 12

Number : 1
Factors : [1]
Factors sum : 1

<?php
/*
  Php program
  Find the sum of factors of a given number
*/
class MyNumber
{
	public 	function factor_sum($number)
	{
		$result = $number;
		echo("Number : ". $number ." ");
		echo("\nFactors : [");
		for ($i = 1; $i <= intval($number / 2); ++$i)
		{
			//Check whether resultant remainder of number divisible by n  is zero or not
			if ($number % $i == 0)
			{
				echo($i .",");
				//Sum Factors
				$result += $i;
			}
		}
		//Given number is itself factor
		echo($number);
		echo("]\n");
		echo("Factors sum : ". $result ."\n\n");
	}
}

function main()
{
	$obj = new MyNumber();
	//Test Cases
	$obj->factor_sum(50);
	$obj->factor_sum(180);
	$obj->factor_sum(11);
	$obj->factor_sum(1);
}
main();

Output

Number : 50
Factors : [1,2,5,10,25,50]
Factors sum : 93

Number : 180
Factors : [1,2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90,180]
Factors sum : 546

Number : 11
Factors : [1,11]
Factors sum : 12

Number : 1
Factors : [1]
Factors sum : 1

/*
  Node Js program
  Find the sum of factors of a given number
*/
class MyNumber
{
	factor_sum(number)
	{
		var result = number;
		process.stdout.write("Number : " + number + " ");
		process.stdout.write("\nFactors : [");
		for (var i = 1; i <= parseInt(number / 2); ++i)
		{
			//Check whether resultant remainder of number divisible by n  is zero or not
			if (number % i == 0)
			{
				process.stdout.write(i + ",");
				//Sum Factors
				result += i;
			}
		}
		//Given number is itself factor
		process.stdout.write(""+number);
		process.stdout.write("]\n");
		process.stdout.write("Factors sum : " + result + "\n\n");
	}
}

function main(args)
{
	var obj = new MyNumber();
	//Test Cases
	obj.factor_sum(50);
	obj.factor_sum(180);
	obj.factor_sum(11);
	obj.factor_sum(1);
}
main();

Output

Number : 50
Factors : [1,2,5,10,25,50]
Factors sum : 93

Number : 180
Factors : [1,2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90,180]
Factors sum : 546

Number : 11
Factors : [1,11]
Factors sum : 12

Number : 1
Factors : [1]
Factors sum : 1

#   Python 3 program
#   Find the sum of factors of a given number

class MyNumber :
	def factor_sum(self, number) :
		result = number
		print("Number : ", number ," ", end = "")
		print("\nFactors : [", end = "")
		i = 1
		while (i <= int(number / 2)) :
			# Check whether resultant remainder of number divisible by n  is zero or not
			if (number % i == 0) :
				print(i ,",", end = "")
				# Sum Factors
				result += i
			
			i += 1
		
		
		# Given number is itself factor
		print(number, end = "")
		print("]\n", end = "")
		print("Factors sum : ", result ,"\n\n", end = "")
	

def main() :
	obj = MyNumber()
	# Test Cases
	obj.factor_sum(50)
	obj.factor_sum(180)
	obj.factor_sum(11)
	obj.factor_sum(1)


if __name__ == "__main__": main()

Output

Number :  50
Factors : [1 ,2 ,5 ,10 ,25 ,50]
Factors sum :  93

Number :  180
Factors : [1 ,2 ,3 ,4 ,5 ,6 ,9 ,10 ,12 ,15 ,18 ,20 ,30 ,36 ,45 ,60 ,90 ,180]
Factors sum :  546

Number :  11
Factors : [1 ,11]
Factors sum :  12

Number :  1
Factors : [1]
Factors sum :  1

#   Ruby program
#   Find the sum of factors of a given number

class MyNumber

	def factor_sum(number)
	
		result = number
		print("Number  : ", number ," ")
		print("\nFactors  : [")
		i = 1
		while (i <= number / 2)
		
			# Check whether resultant remainder of number divisible by n  is zero or not
			if (number % i == 0)
			
				print(i ,",")
				# Sum Factors
				result += i
			end
			i += 1
		end
		# Given number is itself factor
		print(number)
		print("]\n")
		print("Factors sum  : ", result ,"\n\n")
	end
end
def main()

	obj = MyNumber.new()
	# Test Cases
	obj.factor_sum(50)
	obj.factor_sum(180)
	obj.factor_sum(11)
	obj.factor_sum(1)
end
main()

Output

Number  : 50 
Factors  : [1,2,5,10,25,50]
Factors sum  : 93

Number  : 180 
Factors  : [1,2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90,180]
Factors sum  : 546

Number  : 11 
Factors  : [1,11]
Factors sum  : 12

Number  : 1 
Factors  : [1]
Factors sum  : 1


/*
  Scala program
  Find the sum of factors of a given number
*/
class MyNumber
{
	def factor_sum(number: Long): Unit = {
		var result: Long = number;
		print("Number : " + number + " ");
		print("\nFactors : [");
		var i: Int = 1;
		while (i <= (number / 2).toInt)
		{
			//Check whether resultant remainder of number divisible by n  is zero or not
			if (number % i == 0)
			{
				print("" + i + ",");
				//Sum Factors
				result += i;
			}
			i += 1;
		}
		//Given number is itself factor
		print(number);
		print("]\n");
		print("Factors sum : " + result + "\n\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyNumber = new MyNumber();
		//Test Cases
		obj.factor_sum(50);
		obj.factor_sum(180);
		obj.factor_sum(11);
		obj.factor_sum(1);
	}
}

Output

Number : 50
Factors : [1,2,5,10,25,50]
Factors sum : 93

Number : 180
Factors : [1,2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90,180]
Factors sum : 546

Number : 11
Factors : [1,11]
Factors sum : 12

Number : 1
Factors : [1]
Factors sum : 1

/*
  Swift program
  Find the sum of factors of a given number
*/
class MyNumber
{
	func factor_sum(_ number: Int)
	{
		var result: Int = number;
		print("Number : ", number ," ", terminator: "");
		print("\nFactors : [", terminator: "");
		var i: Int = 1;
		while (i <= number / 2)
		{
			//Check whether resultant remainder of number divisible by n  is zero or not
			if (number % i == 0)
			{
				print(i ,",", terminator: "");
				//Sum Factors
				result += i;
			}
			i += 1;
		}
		
		//Given number is itself factor
		print(number, terminator: "");
		print("]\n", terminator: "");
		print("Factors sum : ", result ,"\n\n", terminator: "");
	}
}
func main()
{
	let obj: MyNumber = MyNumber();
	//Test Cases
	obj.factor_sum(50);
	obj.factor_sum(180);
	obj.factor_sum(11);
	obj.factor_sum(1);
}
main();

Output

Number :  50
Factors : [1 ,2 ,5 ,10 ,25 ,50]
Factors sum :  93

Number :  180
Factors : [1 ,2 ,3 ,4 ,5 ,6 ,9 ,10 ,12 ,15 ,18 ,20 ,30 ,36 ,45 ,60 ,90 ,180]
Factors sum :  546

Number :  11
Factors : [1 ,11]
Factors sum :  12

Number :  1
Factors : [1]
Factors sum :  1

Output Explanation

  • factor_sum(50): Number: 50 Factors: [1, 2, 5, 10, 25, 50] Factors sum: 93

  • factor_sum(180): Number: 180 Factors: [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180] Factors sum: 546

  • factor_sum(11): Number: 11 Factors: [1, 11] Factors sum: 12

  • factor_sum(1): Number: 1 Factors: [1] Factors sum: 1

Time Complexity

The time complexity of this algorithm is O(n), where n is the given input number. The for loop runs from 1 to number/2, resulting in a linear time complexity with respect to the input size. For large numbers, the time complexity can be considered approximately O(n/2), which simplifies to O(n) in big O notation.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment