12) Prime Factorization & Divisors
Prime Factorization: Expressing a number as a product of its prime factors.
Example:
Divisors: The divisors of a number are the positive integers that divide the number without leaving a remainder.
Example:
Below is the code snippet for Prime Factorization & Divisors:
#include <iostream>
#include <cmath>
using namespace std;
void primeFactors(int n)
{
// Print the number of 2s that divide n
while (n % 2 == 0) {
cout << 2 << " ";
n /= 2;
}
// n must be odd at this point. So we can skip one
// element (Note i = i +2)
for (int i = 3; i <= sqrt(n); i += 2) {
// While i divides n, print i and divide n
while (n % i == 0) {
cout << i << " ";
n /= i;
}
}
// This condition is to handle the case when n is a
// prime number greater than 2
if (n > 2) {
cout << n;
}
}
// Test the function
int main()
{
primeFactors(315);
return 0;
}
import java.util.*;
public class Main {
public static void primeFactors(int n)
{
// Print the number of 2s that divide n
while (n % 2 == 0) {
System.out.print(2 + " ");
n /= 2;
}
// n must be odd at this point. So we can skip one
// element (Note i = i +2)
for (int i = 3; i <= Math.sqrt(n); i += 2) {
// While i divides n, print i and divide n
while (n % i == 0) {
System.out.print(i + " ");
n /= i;
}
}
// This condition is to handle the case when n is a
// prime number greater than 2
if (n > 2) {
System.out.print(n);
}
}
// Test the function
public static void main(String[] args)
{
primeFactors(315);
}
}
import math
def prime_factors(n):
# Print the number of 2s that divide n
while n % 2 == 0:
print(2, end=" ")
n = n / 2
# n must be odd at this point. So we can skip one element (Note i = i +2)
for i in range(3, int(math.sqrt(n)) + 1, 2):
# While i divides n, print i and divide n
while n % i == 0:
print(i, end=" ")
n = n / i
# This condition is to handle the case when n is a prime number greater than 2
if n > 2:
print(n, end=" ")
# Test the function
prime_factors(315)
function primeFactors(n) {
// Print the number of 2s that divide n
while (n % 2 === 0) {
process.stdout.write('2 ');
n /= 2;
}
// n must be odd at this point. So we can skip one element (Note i = i +2)
for (let i = 3; i <= Math.sqrt(n); i += 2) {
// While i divides n, print i and divide n
while (n % i === 0) {
process.stdout.write(`${i} `);
n /= i;
}
}
// This condition is to handle the case when n is a prime number greater than 2
if (n > 2) {
process.stdout.write(`${n}`);
}
}
// Test the function
primeFactors(315);
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)