Divisors of a number
A divisor is a number that gives remainder as 0 when divided.
As we know the divisors of a number will definitely be lesser or equal to the number, all the numbers between 1 and the number, can be possible divisors of a number, but iterating through the entire number range takes O(n) time complexity, so can we optimize this approach?
The answer is YES it can be optimized to O(sqrt(n)) by careful observation, we can notice that the root of a number actually acts as a splitting part of all the divisors of a number.
Below is the code snippet for Divisors of a number:
void printDivisorsOptimal(int n)
{
cout << "The Divisors of " << n << " are:" << endl;
for (int i = 1; i <= sqrt(n); i++)
if (n % i == 0) {
cout << i << " ";
if (i != n / i)
cout << n / i << " ";
}
cout << "\n";
}
import java.util.*;
public class PrintDivisorsOptimal {
// Function to print the divisors of a number 'n'
static void printDivisorsOptimal(int n) {
System.out.println("The Divisors of " + n + " are:");
// Iterate up to the square root of 'n'
for (int i = 1; i <= Math.sqrt(n); i++) {
// If 'i' divides 'n' evenly
if (n % i == 0) {
// Print the divisor 'i'
System.out.print(i + " ");
// If 'i' is not the square root of 'n', print the other divisor
if (i != n / i) {
System.out.print((n / i) + " ");
}
}
}
System.out.println(); // Print a new line after printing divisors
}
public static void main(String[] args) {
int num = 20; // Replace this number with the desired input
// Call the function to print divisors for the given number 'num'
printDivisorsOptimal(num);
}
}
import math
def print_divisors_optimal(n):
print("The Divisors of", n, "are:")
# Iterate up to the square root of 'n'
for i in range(1, int(math.sqrt(n)) + 1):
# If 'i' divides 'n' evenly
if n % i == 0:
# Print the divisor 'i'
print(i, end=" ")
# If 'i' is not the square root of 'n', print the other divisor
if i != n // i:
print(n // i, end=" ")
print() # Print a new line after printing divisors
if __name__ == "__main__":
num = 20 # Replace this number with the desired input
print_divisors_optimal(num)
using System;
class Program
{
static void PrintDivisorsOptimal(int n)
{
Console.WriteLine($"The Divisors of {n} are:");
for (int i = 1; i <= Math.Sqrt(n); i++)
{
if (n % i == 0)
{
Console.Write(i + " ");
if (i != n / i)
{
Console.Write(n / i + " ");
}
}
}
Console.WriteLine();
}
}
// JavaScript Implementation
function printDivisorsOptimal(n) {
console.log(`The Divisors of ${n} are:`);
for (let i = 1; i <= Math.sqrt(n); i++) {
if (n % i === 0) {
console.log(i);
if (i !== n / i) {
console.log(n / i);
}
}
}
}
const num = 20;
printDivisorsOptimal(num);
// This code is contributed by Sakshi
Maths for Data Structure and Algorithms (DSA) | A Complete Guide
Maths is a fundamental component of learning Data Structure and Algorithms, just like in programming. Maths is primarily used to evaluate the effectiveness of different algorithms. However, there are situations when the answer requires some mathematical understanding or the problem has mathematical characteristics and certain problems demand more than just code. They require a mathematical perspective and a recognition of patterns and characteristics that go beyond the syntax of programming languages. Therefore, understanding maths is essential to know data structures and algorithms. So here in this Maths Guide for Data Structure and Algorithms (DSA), we will be looking into some commonly used concepts of Maths in DSA.
Table of Content
- GCD and HCF (Euclidean Algorithm)
- Divisors of a number
- Prime numbers using Sieve of Eratosthenes
- Square root
- Modular Arithmetic
- Fast Power-Exponentiation by Squaring
- Factorial of a number
- Fibonacci Number
- Catalan Numbers
- Euler Totient Function
- Prime numbers & Primality Tests
- Prime Factorization & Divisors
- Chinese Remainder Theorem
- Practice Problems based on Maths for DSA
- Most Frequently Asked Questions (FAQs)