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
- 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. - Create a function
count_divisor(number)
to count the perfect divisors of a given number. - If the number is less than or equal to 0, return.
- Initialize a
counter
variable to keep track of the count of perfect divisors. - Initialize a loop variable
i
to 1. - Inside the loop, check if
i
is a divisor of the number. If yes, then:- Check if
i
is a perfect square using theis_perfect_square
function. - If yes, print
i
and increment the counter. - Check if
(number / i)
is a perfect square and not equal toi
. - If yes, print
(number / i)
and increment the counter.
- Check if
- 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.
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