Divisors of a number
In this section, we will explore how to find all the divisors of a given number n.
What is the divisor of a number?
Divisors of a given number n are the numbers that can divide it evenly, without leaving a remainder. In other words, we can say if a given number n is divisible by k then we can say k is the divisor of n.
Before learning about divisor we should know how to check whether a number is divisible by another number.
Let us learn this: Check if a number is divisible by k?
Checking if a number is divisible by another number k is a common task in programming and mathematics.
In simple terms, divisibility means that dividing the number by k leaves no remainder.
In Mathematically, we express this as n % k = 0, here modulo operator is being used to find out the remainder when a given number n is divisible by k or not. If this condition holds, then n is divisible by k; otherwise, it is not.
Let us understand it with an example
Let’s consider examples to clarify the concept:
- Example 1: Check if 20 is divisible by 5.
- Since 20 % 5 = 0, 20 is divisible by 5.
- Example 2: Check if 21 is divisible by 5.
- Since 21 % 5 = 1, 21 is not divisible by 5.
Approach for Divisibility Check
- Input: The number n and the divisor k.
- Check Remainder: Use the modulus operator to check if n % k = 0.
- Return Result: If the remainder is zero, the number is divisible by k; otherwise, it is not.
Code Implementation
C++
class Solution{
public:
// Method to check if a number 'n' is divisible by 'k'
bool isDivisible(int n, int k) {
// Check if divisor 'k' is zero to avoid division by zero error
if (k == 0) {
cout << "Error: Division by zero is undefined." << endl;
return false; // Return false if 'k' is zero
}
// Use modulus operator to check if remainder is zero
return n % k == 0; // If remainder is zero, 'n' is divisible by 'k'
}
};Java
public class Solution {
// Method to check if a number 'n' is divisible by 'k'
public static boolean isDivisible(int n, int k) {
// Check if divisor 'k' is zero to avoid division by zero error
if (k == 0) {
System.out.println("Error: Division by zero is undefined.");
return false; // Return false if 'k' is zero
}
// Use modulus operator to check if remainder is zero
return n % k == 0; // If remainder is zero, 'n' is divisible by 'k'
}
}Python
class Solution:
# Method to check if a number 'n' is divisible by 'k'
def is_divisible(self, n, k):
# Check if divisor 'k' is zero to avoid division by zero error
if k == 0:
print("Error: Division by zero is undefined.")
return False # Return False if 'k' is zero
# Use modulus operator to check if remainder is zero
return n % k == 0 # If remainder is zero, 'n' is divisible by 'k'Javascript
class Solution {
// Method to check if a number 'n' is divisible by 'k'
isDivisible(n, k) {
// Check if divisor 'k' is zero to avoid division by zero error
if (k === 0) {
console.log("Error: Division by zero is undefined.");
return false; // Return false if 'k' is zero
}
// Use modulus operator to check if remainder is zero
return n % k === 0; // If remainder is zero, 'n' is divisible by 'k'
}
}
Time Complexity: O(1)
The time complexity of the entire program is O(1), as the operations performed do not depend on the size of the input. The algorithm only runs a fixed number of steps, no matter the values of n and k.
Space Complexity: O(1)
The space complexity of the program is O(1). It does not use any memory that grows with the input size, as it only uses a few fixed variables and objects.
Since we have learned about find the divisibility of a number by another number, now we are ready to learn about divisors
Brute Force Approach
So, the brute force approach to finding the divisors of a number n involves checking each number from 1 to n to see if it divides n evenly. Here’s how it works step by step:
- Start at 1: Begin with the number 1.
- Check each number: For each number i from 1 to n:
- If n divided by i has no remainder (i.e., n % i = 0 ), then i is a divisor of nnn.
- Collect the divisors: Keep track of all numbers i that divide n evenly.
For example, to find the divisors of 12:
- Check 1: 12 % 1 = 0 (1 is a divisor)
- Check 2: 12 % 2 = 0 (2 is a divisor)
- Check 3: 12 % 3 = 0 (3 is a divisor)
- Check 4: 12 % 4 = 0 (4 is a divisor)
- Check 5: 12 % 5 ≠ 0 (5 is not a divisor)
- Check 6: 12 % 6 = 0 (6 is a divisor)
- Check 7: 12 % 7 ≠ 0 (7 is not a divisor)
- Check 8: 12 % 8 ≠ 0 (8 is not a divisor)
- Check 9: 12 % 9 ≠ 0 (9 is not a divisor)
- Check 10: 12 % 10 ≠ 0 (10 is not a divisor)
- Check 11: 12 % 11 ≠ 0 (11 is not a divisor)
- Check 12: 12 % 12 = 0 (12 is a divisor)
So the divisors of 12 are 1, 2, 3, 4, 6, and 12.
This method is functional, however, it becomes inefficient when dealing with larger numbers, particularly when n≥10^8. The reason is that iterating through such large values is computationally expensive and time-consuming, making the approach impractical for handling very large inputs.
Is there a way to optimize it?
Yes, there is! If you look more closely at the divisors of a number, such as 12, you’ll notice something interesting. Let’s list the divisors of 12: 1,2,3,4,6,12.
On closer observation, you can see that these divisors form pairs that multiply to 12.
For instance: 1×12=12, 2×6=12, 3×4=12
This pairing of divisors significantly reduces the number of iterations required to find all divisors. Instead of iterating up to the number itself, you only need to iterate up to the square root of the number.
Why square root of a number?
When you are looking for divisors of a number n, each divisor i has a corresponding pair n/i . For instance, if i divides n, then n/i must also divide n, because i×(n/i)=n.
For example, let's take n=36.
The divisors of 36 are: 1,2,3,4,6,9,12,18,36
We can pair them like this:
- (1, 36)
- (2, 18)
- (3, 12)
- (4, 9)
- (6, 6)
For every divisor i found within this range, its corresponding pair n/i in can also be identified.
Now, observe that one member of each pair is always less than or equal to √n, and the other is greater than or equal to √n. For example, in the case of n=36:
- The divisor 6 is exactly √36.
- The other divisors in the pairs (1, 36), (2, 18), (3, 12), (4, 9) are on opposite sides of √36.
Once you reach √n, you've already considered all the smaller divisors. The larger divisors can be derived directly from the smaller ones. Therefore, you don't need to check beyond √n because, for any divisor i>√n, its corresponding pair n/i in will already have been encountered in previous iterations.
Let us understand it with an Example
Let’s go through the algorithm for n = 36:
- Initialize list: Start with an empty list: divisors = [].
- Square root of 36: Since √36 = 6. So, the loop will run from 1 to 6.
- Iterate from 1 to 6:
- i = 1:
- Check if 36 % 1 == 0. Yes, it is.
- Add 1 to the list: divisors = [1].
- Add 36 / 1 = 36 to the list: divisors = [1, 36].
- i = 2:
- Check if 36 % 2 == 0. Yes, it is.
- Add 2 to the list: divisors = [1, 36, 2].
- Add 36 / 2 = 18 to the list: divisors = [1, 36, 2, 18].
- i = 3:
- Check if 36 % 3 == 0. Yes, it is.
- Add 3 to the list: divisors = [1, 36, 2, 18, 3].
- Add 36 / 3 = 12 to the list: divisors = [1, 36, 2, 18, 3, 12].
- i = 4:
- Check if 36 % 4 == 0. Yes, it is.
- Add 4 to the list: divisors = [1, 36, 2, 18, 3, 12, 4].
- Add 36 / 4 = 9 to the list: divisors = [1, 36, 2, 18, 3, 12, 4, 9].
- i = 5:
- Check if 36 % 5 == 0. No, it’s not.
- i = 6:
- Check if 36 % 6 == 0. Yes, it is.
- Add 6 to the list: divisors = [1, 36, 2, 18, 3, 12, 4, 9, 6].
- Since i == n / i in this case, we don't add it again.
Final divisors list: divisors = [1, 36, 2, 18, 3, 12, 4, 9, 6].
Code for All Languages
C++
class Solution
{
public:
// Function to find divisors of a number n
vector<int> findDivisors(int n)
{
// Declare a vector to store divisors
vector<int> divisors;
// Iterate only up to the square root of n
for (int i = 1; i <= sqrt(n); i++)
{
// Check if i is a divisor of n
if (n % i == 0)
{
// Add divisor i to the vector
divisors.push_back(i);
// Check if i and n/i are different to avoid duplicates
if (i != n / i)
{
// Add the paired divisor n / i to the vector
divisors.push_back(n / i);
}
}
}
// Return the vector containing all divisors
return divisors;
}
};Java
class Solution {
// Function to find divisors of a number n
public List<Integer> findDivisors(int n) {
// Create a list to store divisors
List<Integer> divisors = new ArrayList<>();
// Iterate only up to the square root of n
for (int i = 1; i <= Math.sqrt(n); i++) {
// Check if i is a divisor of n
if (n % i == 0) {
// Add divisor i to the list
divisors.add(i);
// Check if i and n/i are different to avoid duplicates
if (i != n / i) {
// Add the paired divisor n / i to the list
divisors.add(n / i);
}
}
}
// Return the list containing all divisors
return divisors;
}
}Python
class Solution:
# Function to find divisors of a number n
def findDivisors(self, n):
# Create a list to store divisors
divisors = []
# Iterate only up to the square root of n
for i in range(1, int(math.sqrt(n)) + 1):
# Check if i is a divisor of n
if n % i == 0:
# Add divisor i to the list
divisors.append(i)
# Check if i and n/i are different to avoid duplicates
if i != n // i:
# Add the paired divisor n / i to the list
divisors.append(n // i)
# Return the list containing all divisors
return divisors
Javascript
class Solution {
// Function to find divisors of a number n
findDivisors(n) {
// Create an array to store divisors
let divisors = [];
// Iterate only up to the square root of n
for (let i = 1; i <= Math.sqrt(n); i++) {
// Check if i is a divisor of n
if (n % i === 0) {
// Add divisor i to the array
divisors.push(i);
// Check if i and n/i are different to avoid duplicates
if (i !== n / i) {
// Add the paired divisor n / i to the array
divisors.push(n / i);
}
}
}
// Return the array containing all divisors
return divisors;
}
}Time Complexity: O(√n)
- Loop Iteration:
- The loop runs from 1 to √n (because divisors come in pairs, and if i is a divisor, then n/i is another divisor). This results in a loop that executes approximately √n times.
- For each i in this range, we perform:
- A modulus operation (n % i == 0), which takes constant time, i.e., O(1).
- A division operation (n / i), which is also O(1).
- Two potential insertions into the list of divisors, which are O(1) each in the average case.
- Number of Divisors:
- In the worst case, the number of divisors of n is proportional to O(√n) because each divisor pair includes one element that’s less than or equal to √n.
- Therefore, in the worst case, the algorithm can store up to 2√n divisors (since each number i has a corresponding divisor n/i).
Given these points, the loop runs O(√n) times and performs constant-time operations within each iteration.
Hence, the total time complexity is: O(√n)
Space Complexity: O(√n)
- List to Store Divisors:
- The main space usage comes from the divisors list, which stores all the divisors of n.
- In the worst case, the number of divisors is approximately 2√n because for each i, we might add both i and n/i to the list. Therefore, the list can store up to O(2√n) elements.
- Auxiliary Space:
- The algorithm does not use any additional significant data structures apart from the divisors list.
- We are only using a few variables (i, n, and divisors) that take constant space.
Therefore, the total space complexity is dominated by the space required to store the divisors, which is: O(√n)