Skip to main content

Count all perfect divisors of a number

The problem addressed in this code is to count all the perfect divisors of a given number. A perfect divisor is a divisor of a number that is also a perfect square. The goal is to identify and count all the perfect divisors of a given number.

Problem Statement and Description

Given a positive integer, the objective is to find and count all the perfect divisors of that number. A perfect divisor is a divisor of a number that is also a perfect square. For example, for the number 1200, the perfect divisors are 1, 4, 16, 25, 400, and 100.

Idea to Solve the Problem

The problem can be solved by iterating through all possible divisors of the given number and checking if each divisor is also a perfect square. To determine if a number is a perfect square, we can compare its square root with the integer part of its square root. If they are equal, the number is a perfect square.

Pseudocode

is_perfect_square(number):
    x = integer part of sqrt(number)
    if x * x == number:
        return true
    else:
        return false

count_divisor(number):
    if number <= 0:
        return
    
    counter = 0
    i = 1
    
    Print "Given number:", number
    Print "Perfect divisor ["
    
    while i * i <= number:
        if number % i == 0:
            if is_perfect_square(i):
                Print i
                increment counter
            if (number / i) != i and is_perfect_square(number / i):
                Print number / i
                increment counter
        increment i
    
    Print "]"
    Print "Result:", counter

Algorithm Explanation

  1. Create a function is_perfect_square(number) that checks if a given number is a perfect square. Compute the integer part of the square root of the number and compare it with the number itself.
  2. Create a function count_divisor(number) to count the perfect divisors of a given number.
  3. If the number is less than or equal to 0, return.
  4. Initialize a counter variable to keep track of the count of perfect divisors.
  5. Initialize a loop variable i to 1.
  6. Inside the loop, check if i is a divisor of the number. If yes, then:
    • Check if i is a perfect square using the is_perfect_square function.
    • If yes, print i and increment the counter.
    • Check if (number / i) is a perfect square and not equal to i.
    • If yes, print (number / i) and increment the counter.
  7. After the loop, print the calculated result.

Code Solution

// C program
// Count all perfect divisors of a number
#include <stdio.h>

#include <math.h>

//This are used to detect number is an perfect square or not
int is_perfect_square(int number)
{
	int x = (int) sqrt(number);
	if (x * x == number)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
//Find the all perfect divisors of given number
void count_divisor(int number)
{
	if (number <= 0)
	{
		return;
	}
	int counter = 0;
	//Loop controlling variable
	int i = 1;
	printf("\n Given number : %d ", number);
	printf("\n Perfect divisor [");
	while (i * i <= number)
	{
		if (number % i == 0)
		{
			if (is_perfect_square(i))
			{
				printf(" %d", i);
				counter++;
			}
			if ((number / i) != i && is_perfect_square(number / i))
			{
				// When number/i is perfect and number/i is not equal to [i]
				// Get new divisor
				counter++;
				printf(" %d", number / i);
			}
		}
		i++;
	}
	printf(" ]");
	printf("\n Result : %d\n", counter);
}
int main()
{
	//Test case
	count_divisor(81);
	count_divisor(1200);
	return 0;
}

Output

 Given number : 81
 Perfect divisor [ 1 81 9 ]
 Result : 3

 Given number : 1200
 Perfect divisor [ 1 400 4 100 16 25 ]
 Result : 6
// Java program 
// Count all perfect divisors of a number
class PerfectDivisors
{
	//This are used to detect number is an perfect square or not
	public boolean is_perfect_square(int number)
	{
		int x = (int) Math.sqrt(number);
		if (x * x == number)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//Find the all perfect divisors of given number
	public void count_divisor(int number)
	{
		if (number <= 0)
		{
			return;
		}
		int counter = 0;
		//Loop controlling variable
		int i = 1;
		System.out.print("\n Given number : " + number);
		System.out.print("\n Perfect divisor [");
		while (i * i <= number)
		{
			if (number % i == 0)
			{
				if (is_perfect_square(i))
				{
					System.out.print(" " + i);
					counter++;
				}
				if ((number / i) != i && is_perfect_square(number / i))
				{
					// When number/i is perfect and number/i is not equal to [i]
					// Get new divisor
					counter++;
					System.out.print(" " + number / i);
				}
			}
			i++;
		}
		System.out.print(" ]");
		System.out.print("\n Result : " + counter + "\n");
	}
	public static void main(String[] args)
	{
		PerfectDivisors obj = new PerfectDivisors();
		//Test case
		obj.count_divisor(81);
		obj.count_divisor(1200);
	}
}

Output

 Given number : 81
 Perfect divisor [ 1 81 9 ]
 Result : 3

 Given number : 1200
 Perfect divisor [ 1 400 4 100 16 25 ]
 Result : 6
//Include header file
#include <iostream>
#include<math.h>
using namespace std;

// C++ program 
// Count all perfect divisors of a number

class PerfectDivisors
{
	public:
		//This are used to detect number is an perfect square or not
		bool is_perfect_square(int number)
		{
			int x = (int) sqrt(number);
			if (x *x == number)
			{
				return true;
			}
			else
			{
				return false;
			}
		}
	//Find the all perfect divisors of given number
	void count_divisor(int number)
	{
		if (number <= 0)
		{
			return;
		}
		int counter = 0;
		//Loop controlling variable
		int i = 1;
		cout << "\n Given number : " << number;
		cout << "\n Perfect divisor [";
		while (i *i <= number)
		{
			if (number % i == 0)
			{
				if (this->is_perfect_square(i))
				{
					cout << " " << i;
					counter++;
				}
				if ((number / i) != i && this->is_perfect_square(number / i))
				{
					// When number/i is perfect and number/i is not equal to [i]
					// Get new divisor
					counter++;
					cout << " " << number / i;
				}
			}
			i++;
		}
		cout << " ]";
		cout << "\n Result : " << counter << "\n";
	}
};
int main()
{
	PerfectDivisors obj = PerfectDivisors();
	//Test case
	obj.count_divisor(81);
	obj.count_divisor(1200);
	return 0;
}

Output

 Given number : 81
 Perfect divisor [ 1 81 9 ]
 Result : 3

 Given number : 1200
 Perfect divisor [ 1 400 4 100 16 25 ]
 Result : 6
//Include namespace system
using System;

// C# program 
// Count all perfect divisors of a number

class PerfectDivisors
{
	//This are used to detect number is an perfect square or not
	public Boolean is_perfect_square(int number)
	{
		int x = (int) Math.Sqrt(number);
		if (x * x == number)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//Find the all perfect divisors of given number
	public void count_divisor(int number)
	{
		if (number <= 0)
		{
			return;
		}
		int counter = 0;
		//Loop controlling variable
		int i = 1;
		Console.Write("\n Given number : " + number);
		Console.Write("\n Perfect divisor [");
		while (i * i <= number)
		{
			if (number % i == 0)
			{
				if (is_perfect_square(i))
				{
					Console.Write(" " + i);
					counter++;
				}
				if ((number / i) != i && is_perfect_square(number / i))
				{
					// When number/i is perfect and number/i is not equal to [i]
					// Get new divisor
					counter++;
					Console.Write(" " + number / i);
				}
			}
			i++;
		}
		Console.Write(" ]");
		Console.Write("\n Result : " + counter + "\n");
	}
	public static void Main(String[] args)
	{
		PerfectDivisors obj = new PerfectDivisors();
		//Test case
		obj.count_divisor(81);
		obj.count_divisor(1200);
	}
}

Output

 Given number : 81
 Perfect divisor [ 1 81 9 ]
 Result : 3

 Given number : 1200
 Perfect divisor [ 1 400 4 100 16 25 ]
 Result : 6
<?php
// Php program 
// Count all perfect divisors of a number
class PerfectDivisors
{
	//This are used to detect number is an perfect square or not
	public	function is_perfect_square($number)
	{
		$x = intval(sqrt($number));
		if ($x * $x == $number)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//Find the all perfect divisors of given number
	public	function count_divisor($number)
	{
		if ($number <= 0)
		{
			return;
		}
		$counter = 0;
		//Loop controlling variable
		$i = 1;
		echo "\n Given number : ". $number;
		echo "\n Perfect divisor [";
		while ($i * $i <= $number)
		{
			if ($number % $i == 0)
			{
				if ($this->is_perfect_square($i))
				{
					echo " ". $i;
					$counter++;
				}
				if ((intval($number / $i)) != $i && $this->is_perfect_square(intval($number / $i)))
				{
					// When number/i is perfect and number/i is not equal to [i]
					// Get new divisor
					$counter++;
					echo " ". intval($number / $i);
				}
			}
			$i++;
		}
		echo " ]";
		echo "\n Result : ". $counter ."\n";
	}
}

function main()
{
	$obj = new PerfectDivisors();
	//Test case
	$obj->count_divisor(81);
	$obj->count_divisor(1200);
}
main();

Output

 Given number : 81
 Perfect divisor [ 1 81 9 ]
 Result : 3

 Given number : 1200
 Perfect divisor [ 1 400 4 100 16 25 ]
 Result : 6
// Node Js program 
// Count all perfect divisors of a number
class PerfectDivisors
{
	//This are used to detect number is an perfect square or not
	is_perfect_square(number)
	{
		var x = parseInt(Math.sqrt(number));
		if (x * x == number)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//Find the all perfect divisors of given number
	count_divisor(number)
	{
		if (number <= 0)
		{
			return;
		}
		var counter = 0;
		//Loop controlling variable
		var i = 1;
		process.stdout.write("\n Given number : " + number);
		process.stdout.write("\n Perfect divisor [");
		while (i * i <= number)
		{
			if (number % i == 0)
			{
				if (this.is_perfect_square(i))
				{
					process.stdout.write(" " + i);
					counter++;
				}
				if ((parseInt(number / i)) != i && this.is_perfect_square(parseInt(number / i)))
				{
					// When number/i is perfect and number/i is not equal to [i]
					// Get new divisor
					counter++;
					process.stdout.write(" " + parseInt(number / i));
				}
			}
			i++;
		}
		process.stdout.write(" ]");
		process.stdout.write("\n Result : " + counter + "\n");
	}
}

function main()
{
	var obj = new PerfectDivisors();
	//Test case
	obj.count_divisor(81);
	obj.count_divisor(1200);
}
main();

Output

 Given number : 81
 Perfect divisor [ 1 81 9 ]
 Result : 3

 Given number : 1200
 Perfect divisor [ 1 400 4 100 16 25 ]
 Result : 6
import math
#  Python 3 program 
#  Count all perfect divisors of a number
class PerfectDivisors :
	# This are used to detect number is an perfect square or not
	def is_perfect_square(self, number) :
		x = int(math.sqrt(number))
		if (x * x == number) :
			return True
		else :
			return False
		
	
	# Find the all perfect divisors of given number
	def count_divisor(self, number) :
		if (number <= 0) :
			return
		
		counter = 0
		# Loop controlling variable
		i = 1
		print("\n Given number : ", number, end = "")
		print("\n Perfect divisor [", end = "")
		while (i * i <= number) :
			if (number % i == 0) :
				if (self.is_perfect_square(i)) :
					print(" ", i, end = "")
					counter += 1
				
				if ((int(number / i)) != i and self.is_perfect_square(int(number / i))) :
					#  When number/i is perfect and number/i is not equal to [i]
					#  Get new divisor
					counter += 1
					print(" ", int(number / i), end = "")
				
			
			i += 1
		
		print(" ]", end = "")
		print("\n Result : ", counter ,"\n", end = "")
	

def main() :
	obj = PerfectDivisors()
	# Test case
	obj.count_divisor(81)
	obj.count_divisor(1200)

if __name__ == "__main__": main()

Output

 Given number :  81
 Perfect divisor [  1  81  9 ]
 Result :  3

 Given number :  1200
 Perfect divisor [  1  400  4  100  16  25 ]
 Result :  6
#  Ruby program 
#  Count all perfect divisors of a number

class PerfectDivisors 
	# This are used to detect number is an perfect square or not
	def is_perfect_square(number) 
		x = (Math.sqrt(number)).to_i
		if (x * x == number) 
			return true
		else 
			return false
		end

	end

	# Find the all perfect divisors of given number
	def count_divisor(number) 
		if (number <= 0) 
			return
		end

		counter = 0
		# Loop controlling variable
		i = 1
		print("\n Given number : ", number)
		print("\n Perfect divisor [")
		while (i * i <= number) 
			if (number % i == 0) 
				if (self.is_perfect_square(i)) 
					print(" ", i)
					counter += 1
				end

				if ((number / i) != i && self.is_perfect_square(number / i)) 
					#  When number/i is perfect and number/i is not equal to [i]
					#  Get new divisor
					counter += 1
					print(" ", number / i)
				end

			end

			i += 1
		end

		print(" ]")
		print("\n Result : ", counter ,"\n")
	end

end

def main() 
	obj = PerfectDivisors.new()
	# Test case
	obj.count_divisor(81)
	obj.count_divisor(1200)
end

main()

Output

 Given number : 81
 Perfect divisor [ 1 81 9 ]
 Result : 3

 Given number : 1200
 Perfect divisor [ 1 400 4 100 16 25 ]
 Result : 6

// Scala program 
// Count all perfect divisors of a number
class PerfectDivisors
{
	//This are used to detect number is an perfect square or not
	def is_perfect_square(number: Int): Boolean = {
		var x: Int = (Math.sqrt(number)).toInt;
		if (x * x == number)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//Find the all perfect divisors of given number
	def count_divisor(number: Int): Unit = {
		if (number <= 0)
		{
			return;
		}
		var counter: Int = 0;
		//Loop controlling variable
		var i: Int = 1;
		print("\n Given number : " + number);
		print("\n Perfect divisor [");
		while (i * i <= number)
		{
			if (number % i == 0)
			{
				if (is_perfect_square(i))
				{
					print(" " + i);
					counter += 1;
				}
				if (((number / i).toInt) != i && is_perfect_square((number / i).toInt))
				{
					// When number/i is perfect and number/i is not equal to [i]
					// Get new divisor
					counter += 1;
					print(" " + (number / i).toInt);
				}
			}
			i += 1;
		}
		print(" ]");
		print("\n Result : " + counter + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: PerfectDivisors = new PerfectDivisors();
		//Test case
		obj.count_divisor(81);
		obj.count_divisor(1200);
	}
}

Output

 Given number : 81
 Perfect divisor [ 1 81 9 ]
 Result : 3

 Given number : 1200
 Perfect divisor [ 1 400 4 100 16 25 ]
 Result : 6
import Foundation

// Swift 4 program 
// Count all perfect divisors of a number

class PerfectDivisors
{
	//This are used to detect number is an perfect square or not
	func is_perfect_square(_ number: Int) -> Bool
	{
		let x: Int = Int(sqrt(Double(number)));
        if (x * x == number)
        {
            return true;
        }
        else
        {
            return false;
        }
	}
//Find the all perfect divisors of given number
func count_divisor(_ number: Int)
{
	if (number <= 0)
	{
		return;
	}
	var counter: Int = 0;
	//Loop controlling variable
	var i: Int = 1;
	print("\n Given number : ", number, terminator: "");
	print("\n Perfect divisor [", terminator: "");
	while (i * i <= number)
	{
		if (number % i == 0)
		{
			if (self.is_perfect_square(i))
			{
				print(" ", i, terminator: "");
				counter += 1;
			}
			if ((number / i) != i && self.is_perfect_square(number / i))
			{
				// When number/i is perfect and number/i is not equal to [i]// Get new divisor
				counter += 1;
				print(" ", number / i, terminator: "");
			}
		}
		i += 1;
	}
	print(" ]", terminator: "");
	print("\n Result : ", counter ,"\n", terminator: "");
}
}
func main()
{
	let obj: PerfectDivisors = PerfectDivisors();
	//Test case
	obj.count_divisor(81);
	obj.count_divisor(1200);
}
main();

Output

 Given number :  81
 Perfect divisor [  1  81  9 ]
 Result :  3

 Given number :  1200
 Perfect divisor [  1  400  4  100  16  25 ]
 Result :  6

Resultant Output Explanation

Using the provided test cases (81 and 1200), the output of the code will be:

Given number : 81
Perfect divisor [ 1 9 81 ]
Result : 3

Given number : 1200
Perfect divisor [ 1 4 16 25 400 100 ]
Result : 6

These results indicate that the perfect divisors of 81 are 1, 9, and 81, resulting in a count of 3 perfect divisors. Similarly, the perfect divisors of 1200 are 1, 4, 16, 25, 400, and 100, resulting in a count of 6 perfect divisors.

Time Complexity Analysis

For a given number n, the algorithm iterates through all possible divisors from 1 to the square root of n. Inside the loop, constant-time operations are performed to check if a number is a perfect square and to update the counter. Therefore, the time complexity of the algorithm is O(sqrt(n)), where n is the given number.

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