Skip to main content

Find the factors of a number

Finding factors of a number is a common mathematical problem. Factors of a number are the positive integers that divide the number without leaving any remainder. In this article, we will explore a C program to find the factors of a given number. We will provide a suitable example to illustrate the problem, present the standard pseudocode, explain the algorithm with proper explanations, and analyze the resultant output. Additionally, we will discuss the time complexity of the code.

Problem Statement

Given a positive integer 'n', we want to find all its factors and display them in ascending order.

Example: Let's take the number 24 as an example to illustrate the problem. The factors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24. These numbers divide 24 without leaving any remainder.

Standard Pseudocode: Below is the standard pseudocode to find the factors of a given number 'n':

function find_factors(n):
    factors = []
    for i from 1 to n:
        if n is divisible by i:
            add i to factors
    return factors

Algorithm Explanation

  1. Start by defining a function find_factors(n) that takes an integer 'n' as input and returns a list of factors.
  2. Create an empty list factors to store the factors of the given number.
  3. Use a loop that iterates from 1 to 'n' (inclusive).
  4. For each iteration, check if 'n' is divisible by the current number (i.e., 'i') without leaving any remainder.
  5. If 'n' is divisible by 'i', add 'i' to the list factors.
  6. After the loop, return the list factors containing all the factors.

Code Solution

Here given code implementation process.

//C Program
//Find the factor of a number
#include <stdio.h>

void find_factor(int number)
{
	printf("\nNumber [%d] : { ", number);
	int auxiliary = 1;
	while (auxiliary <= number / 2)
	{
		//Compare the given number, is divisible by auxiliary number or not
		if (number % auxiliary == 0)
		{
			printf("%d,", auxiliary);
		}
		auxiliary++;
	}
	printf("%d }\n", number);
}
int main()
{
	//Test Case 
	find_factor(145);
	find_factor(12);
	find_factor(2020);
	find_factor(11532);
	return 0;
}

Output

Number [145] : { 1,5,29,145 }

Number [12] : { 1,2,3,4,6,12 }

Number [2020] : { 1,2,4,5,10,20,101,202,404,505,1010,2020 }

Number [11532] : { 1,2,3,4,6,12,31,62,93,124,186,372,961,1922,2883,3844,5766,11532 }
/*
  C++ Program
  Find the factor of a number
*/
#include<iostream>

using namespace std;
class MyNumber
{
	public: void find_factor(int number)
	{
		cout << "\nNumber [" << number << "] : { ";
		int auxiliary = 1;
		while (auxiliary <= number / 2)
		{
			//Compare the given number, is divisible by auxiliary number or not
			if (number % auxiliary == 0)
			{
				cout << "" << auxiliary << ",";
			}
			auxiliary++;
		}
		cout << "" << number << " }\n";
	}
};
int main()
{
	MyNumber obj =  MyNumber();
	//Test Case 
	obj.find_factor(145);
	obj.find_factor(12);
	obj.find_factor(2020);
	obj.find_factor(11532);
	return 0;
}

Output

Number [145] : { 1,5,29,145 }

Number [12] : { 1,2,3,4,6,12 }

Number [2020] : { 1,2,4,5,10,20,101,202,404,505,1010,2020 }

Number [11532] : { 1,2,3,4,6,12,31,62,93,124,186,372,961,1922,2883,3844,5766,11532 }
/*
  Java Program
  Find the factor of a number
*/
public class MyNumber
{
  public void find_factor(int number)
  {
    System.out.print("\nNumber ["+number+"] : { ");
    int auxiliary = 1;
    while (auxiliary <= number / 2)
    {
      //Compare the given number, is divisible by auxiliary number or not
      if (number % auxiliary == 0)
      {
        System.out.print(""+auxiliary+",");
      }
      auxiliary++;
    }
    System.out.print(""+number+" }\n" );
  }
  
  public static void main(String[] args)
  {
    MyNumber obj = new MyNumber();
    //Test Case 
    obj.find_factor(145);
    obj.find_factor(12);
    obj.find_factor(2020);
    obj.find_factor(11532);
  }
}

Output

Number [145] : { 1,5,29,145 }

Number [12] : { 1,2,3,4,6,12 }

Number [2020] : { 1,2,4,5,10,20,101,202,404,505,1010,2020 }

Number [11532] : { 1,2,3,4,6,12,31,62,93,124,186,372,961,1922,2883,3844,5766,11532 }
/*
  C# Program
  Find the factor of a number
*/
using System;
public class MyNumber
{
	public void find_factor(int number)
	{
		Console.Write("\nNumber [" + number + "] : { ");
		int auxiliary = 1;
		while (auxiliary <= number / 2)
		{
			//Compare the given number, is divisible by auxiliary number or not
			if (number % auxiliary == 0)
			{
				Console.Write("" + auxiliary + ",");
			}
			auxiliary++;
		}
		Console.Write("" + number + " }\n");
	}
	public static void Main(String[] args)
	{
		MyNumber obj = new MyNumber();
		//Test Case 
		obj.find_factor(145);
		obj.find_factor(12);
		obj.find_factor(2020);
		obj.find_factor(11532);
	}
}

Output

Number [145] : { 1,5,29,145 }

Number [12] : { 1,2,3,4,6,12 }

Number [2020] : { 1,2,4,5,10,20,101,202,404,505,1010,2020 }

Number [11532] : { 1,2,3,4,6,12,31,62,93,124,186,372,961,1922,2883,3844,5766,11532 }
<?php
/*
  Php Program
  Find the factor of a number
*/
class MyNumber
{
	public 	function find_factor($number)
	{
		echo("\nNumber [". $number ."] : { ");
		$auxiliary = 1;
		while ($auxiliary <= intval($number / 2))
		{
			//Compare the given number, is divisible by auxiliary number or not
			if ($number % $auxiliary == 0)
			{
				echo("". $auxiliary .",");
			}
			$auxiliary++;
		}
		echo("". $number ." }\n");
	}
}

function main()
{
	$obj = new MyNumber();
	//Test Case 
	$obj->find_factor(145);
	$obj->find_factor(12);
	$obj->find_factor(2020);
	$obj->find_factor(11532);
}
main();

Output

Number [145] : { 1,5,29,145 }

Number [12] : { 1,2,3,4,6,12 }

Number [2020] : { 1,2,4,5,10,20,101,202,404,505,1010,2020 }

Number [11532] : { 1,2,3,4,6,12,31,62,93,124,186,372,961,1922,2883,3844,5766,11532 }
/*
  Node Js Program
  Find the factor of a number
*/
class MyNumber
{
	find_factor(number)
	{
		process.stdout.write("\nNumber [" + number + "] : { ");
		var auxiliary = 1;
		while (auxiliary <= parseInt(number / 2))
		{
			//Compare the given number, is divisible by auxiliary number or not
			if (number % auxiliary == 0)
			{
				process.stdout.write("" + auxiliary + ",");
			}
			auxiliary++;
		}
		process.stdout.write("" + number + " }\n");
	}
}

function main(args)
{
	var obj = new MyNumber();
	//Test Case 
	obj.find_factor(145);
	obj.find_factor(12);
	obj.find_factor(2020);
	obj.find_factor(11532);
}
main();

Output

Number [145] : { 1,5,29,145 }

Number [12] : { 1,2,3,4,6,12 }

Number [2020] : { 1,2,4,5,10,20,101,202,404,505,1010,2020 }

Number [11532] : { 1,2,3,4,6,12,31,62,93,124,186,372,961,1922,2883,3844,5766,11532 }
#   Python 3 Program
#   Find the factor of a number

class MyNumber :
	def find_factor(self, number) :
		print("\nNumber [", number ,"] : { ", end = "")
		auxiliary = 1
		while (auxiliary <= int(number / 2)) :
			# Compare the given number, is divisible by auxiliary number or not
			if (number % auxiliary == 0) :
				print( auxiliary ,",", end = "")
			
			auxiliary += 1
		
		print("", number,end=" }" )
	

def main() :
	obj = MyNumber()
	# Test Case 
	obj.find_factor(145)
	obj.find_factor(12)
	obj.find_factor(2020)
	obj.find_factor(11532)


if __name__ == "__main__": main()

Output

Number [ 145 ] : { 1 ,5 ,29 , 145 }
Number [ 12 ] : { 1 ,2 ,3 ,4 ,6 , 12 }
Number [ 2020 ] : { 1 ,2 ,4 ,5 ,10 ,20 ,101 ,202 ,404 ,505 ,1010 , 2020 }
Number [ 11532 ] : { 1 ,2 ,3 ,4 ,6 ,12 ,31 ,62 ,93 ,124 ,186 ,372 ,961 ,1922 ,2883 ,3844 ,5766 , 11532 }
#   Ruby Program
#   Find the factor of a number

class MyNumber

	def find_factor(number)
	
		print("\nNumber [", number ,"]  : { ")
		auxiliary = 1
		while (auxiliary <= number / 2)
		
			# Compare the given number, is divisible by auxiliary number or not
			if (number % auxiliary == 0)
			
				print("", auxiliary ,",")
			end
			auxiliary += 1
		end
		print("", number ," }\n")
	end
end
def main()

	obj = MyNumber.new()
	# Test Case 
	obj.find_factor(145)
	obj.find_factor(12)
	obj.find_factor(2020)
	obj.find_factor(11532)
end
main()

Output

Number [145]  : { 1,5,29,145 }

Number [12]  : { 1,2,3,4,6,12 }

Number [2020]  : { 1,2,4,5,10,20,101,202,404,505,1010,2020 }

Number [11532]  : { 1,2,3,4,6,12,31,62,93,124,186,372,961,1922,2883,3844,5766,11532 }

/*
  Scala Program
  Find the factor of a number
*/
class MyNumber
{
	def find_factor(number: Int): Unit = {
		print("\nNumber [" + number + "] : { ");
		var auxiliary: Int = 1;
		while (auxiliary <= (number / 2).toInt)
		{
			//Compare the given number, is divisible by auxiliary number or not
			if (number % auxiliary == 0)
			{
				print("" + auxiliary + ",");
			}
			auxiliary += 1;
		}
		print("" + number + " }\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyNumber = new MyNumber();
		//Test Case 
		obj.find_factor(145);
		obj.find_factor(12);
		obj.find_factor(2020);
		obj.find_factor(11532);
	}
}

Output

Number [145] : { 1,5,29,145 }

Number [12] : { 1,2,3,4,6,12 }

Number [2020] : { 1,2,4,5,10,20,101,202,404,505,1010,2020 }

Number [11532] : { 1,2,3,4,6,12,31,62,93,124,186,372,961,1922,2883,3844,5766,11532 }
/*
  Swift Program
  Find the factor of a number
*/
class MyNumber
{
	func find_factor(_ number: Int)
	{
		print("\nNumber [", number ,"] : { ", terminator: "");
		var auxiliary: Int = 1;
		while (auxiliary <= number / 2)
		{
			//Compare the given number, is divisible by auxiliary number or not
			if (number % auxiliary == 0)
			{
				print("", auxiliary ,",", terminator: "");
			}
			auxiliary += 1;
		}
		print( number ,"}\n", terminator: "");
	}
}
func main()
{
	let obj: MyNumber = MyNumber();
	//Test Case 
	obj.find_factor(145);
	obj.find_factor(12);
	obj.find_factor(2020);
	obj.find_factor(11532);
}
main();

Output

Number [ 145 ] : {  1 , 5 , 29 ,145 }

Number [ 12 ] : {  1 , 2 , 3 , 4 , 6 ,12 }

Number [ 2020 ] : {  1 , 2 , 4 , 5 , 10 , 20 , 101 , 202 , 404 , 505 , 1010 ,2020 }

Number [ 11532 ] : {  1 , 2 , 3 , 4 , 6 , 12 , 31 , 62 , 93 , 124 , 186 , 372 , 961 , 1922 , 2883 , 3844 , 5766 ,11532 }

C Code Explanation: The provided C program follows the above pseudocode to find the factors of a given number. The find_factor function takes an integer number as input and prints the factors of that number. The main function tests the find_factor function with four test cases: 145, 12, 2020, and 11532.

Output Explanation

For each test case, the program prints the number and its factors in ascending order within curly braces. The output is correct as it lists all the factors for each test case.

  • Test Case 1: find_factor(145) Output: Number [145] : { 1, 5, 29, 145 } Explanation: The factors of 145 are 1, 5, 29, and 145.

  • Test Case 2: find_factor(12) Output: Number [12] : { 1, 2, 3, 4, 6, 12 } Explanation: The factors of 12 are 1, 2, 3, 4, 6, and 12.

  • Test Case 3: find_factor(2020) Output: Number [2020] : { 1, 2, 4, 5, 10, 20, 101, 202, 404, 505, 1010, 2020 } Explanation: The factors of 2020 are 1, 2, 4, 5, 10, 20, 101, 202, 404, 505, 1010, and 2020.

  • Test Case 4: find_factor(11532) Output: Number [11532] : { 1, 2, 3, 4, 6, 12, 31, 62, 93, 124, 186, 372, 961, 1922, 2883, 3844, 5766, 11532 } Explanation: The factors of 11532 are 1, 2, 3, 4, 6, 12, 31, 62, 93, 124, 186, 372, 961, 1922, 2883, 3844, 5766, and 11532.

Time Complexity

The time complexity of the provided code is O(n), where 'n' is the given number. The function find_factors iterates from 1 to 'n' to find all the factors, making it linear in the input size. The loop runs approximately 'n/2' times, which is still linear. Therefore, the overall time complexity of the algorithm is O(n).

Finally

In this article, we discussed the problem of finding factors of a number. We provided a C program with appropriate explanations and a suitable example to demonstrate the concept. The code uses a simple algorithm with linear time complexity to find all the factors of a given number. The output for the provided test cases is correct, and the program works efficiently for larger numbers as well.

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