Mathematical and Geometric Algorithms – Data Structure and Algorithm Tutorials

Read

Discuss

Very often we come across topics in DSA that are based on Mathematics. Such topics can be described as Mathematical and Geometrical Algorithms, and are very vital parts of the Data Structures and Algorithms Journey. In this tutorial, we will discuss in detail What are Mathematical and Geometrical Algorithms, When to use them, and how to make use of these algorithms in DSA.

Introduction to Mathematical and Geometrical Algorithms
What are Mathematical Algorithms?
- What are some use cases of Mathematical Algorithms?
- Some important Mathematical Algorithms:
  - Euclid Algorithm:
  - Modular Arithmetic:
  - Binary Exponentiation:
  - Modular Exponentiation:
  - Sieve of Eratosthenes:
- Other useful Mathematical Concepts for Competitive Programming:
  - GCD and LCM:
  - Number System:
  - Prime Numbers:
  - Permutation and Combination:
  - Set theory:
What are Geometric Algorithms?
- Some use cases of Geometric Algorithms:
- Some important Geometric Algorithms and Concepts:
  - Pattern Printing:
  - Convex Hull

Let us first begin with Mathematical Algorithms.

What are Mathematical Algorithms?

Mathematical algorithm can be defined as an algorithm or procedure which is utilized to solve a mathematical problem, or mathematical problem which can be solved using DSA.

In the field of DSA, mathematical algorithms refer to those algorithms which are generally used to solve problems related to the field of computer science.

What are some use cases of Mathematical Algorithms?

It is a very useful topic for solving problems of computer science and also has vast applications in competitive programming. Some of them are mentioned below:

1. Problem-Solving: It is mostly used in solving complex mathematical ideas in mathematics and computer science.

2. Competitive Programming: Algorithms like Sieve of Eratosthenes, Euclid algorithm, Binary exponentiation are some of the most common topics used in competitive programming.

3. Recurrence relation: A lot of problems in DSA require the usage of recursion. Using the knowledge of mathematics several recurrence relations can be turned into mathematical formulae which makes solving the problem quite an easy task.

4. Heavy calculation: Problems containing complex mathematical concepts and heavy calculations are easily done in comparatively less time using these algorithms instead of manual calculations.

5. Statistics: Mathematical algorithms are also important for data processing, i.e., for converting raw data into useful information and also for analyzing them.

Some important Mathematical Algorithms:

Euclid Algorithm:

This is an algorithm to find the GCD of two numbers efficiently. A simple way to find the GCD of two numbers is to factorize both numbers and multiply the common factors. This algorithm is based on the following facts:

If one number is 0 and the other is non-zero, the non-zero number is the GCD
If we subtract a smaller number from a larger one, GCD doesn’t change. So if we repeatedly keep subtracting the smaller from the larger we end up with GCD (the larger is the GCD).
We can subtract the smaller number (say b) from the larger number (say a), at most floor(a/b) times. So after repeated subtraction, ‘a’ becomes a – b*floor(a/b) which is a%b. Instead of repeated subtraction we can do a%b and stop when it becomes 0 [then b becomes the GCD].

Code implementation of Euclid Algorithm:

C++

// C++ program to demonstrate Basic Euclidean Algorithm 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to return gcd of a and b 
int gcd(int a, int b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
  
// Driver Code 
int main() 
{ 
    int a = 10, b = 15; 
  
    // Function call 
    cout << "GCD(" << a << ", " << b << ") = " << gcd(a, b) 
         << endl; 
    return 0; 
}

Java

// Java program to demonstrate Basic Euclidean Algorithm 
import java.lang.*; 
import java.util.*; 
  
class GFG { 
  
    // Function to return gcd of a and b 
    public static int gcd(int a, int b) 
    { 
        if (a == 0) 
            return b; 
  
        return gcd(b % a, a); 
    } 
  
    // Driver code 
    public static void main(String[] args) 
    { 
        int a = 10, b = 15, g; 
  
        // Function call 
        g = gcd(a, b); 
        System.out.println("GCD(" + a + ", " + b 
                           + ") = " + g); 
    } 
}

Python3

# Python3 program to demonstrate Basic Euclidean Algorithm 
  
  
# Function to return gcd of a and b 
def gcd(a, b): 
    if a == 0: 
        return b 
  
    return gcd(b % a, a) 
  
  
# Driver code 
if __name__ == "__main__": 
    a = 10
    b = 15
  
    # Function call 
    print("GCD(",a,",", b,") = ", gcd(a, b)) 

C#

// C# program to demonstrate Basic Euclidean Algorithm 
using System; 
  
class GFG { 
      
    // Function to return gcd of a and b 
    public static int gcd(int a, int b) 
    { 
        if (a == 0) 
            return b; 
  
        return gcd(b % a, a); 
    } 
  
    // Driver Code 
    static public void Main() 
    { 
        int a = 10, b = 15, g; 
        g = gcd(a, b); 
        
        // Function call 
        Console.WriteLine("GCD(" + a + ", " + b 
                        + ") = " + g); 
    } 
}

Javascript

// JavaScript program to demonstrate Basic Euclidean Algorithm 
  
// Function to return gcd of a and b 
function gcd( a, b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
  
// Driver Code 
let a = 10, b = 15; 
  
// Function call 
console.log( "GCD(" + a + ", "
        + b + ") = " + gcd(a, b));

C

// C program to demonstrate Basic Euclidean Algorithm 
#include <stdio.h> 
  
// Function to return gcd of a and b 
int gcd(int a, int b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
  
// Driver code 
int main() 
{ 
    int a = 10, b = 15; 
  
    // Function call 
    printf("GCD(%d, %d) = %d\n", a, b, gcd(a, b)); 
    return 0; 
}

PHP

<?php 
// PHP program to demonstrate Basic Euclidean Algorithm 
  
// Function to return gcd of a and b 
function gcd($a, $b) 
{ 
    if ($a == 0) 
        return $b; 
    return gcd($b % $a, $a); 
} 
  
// Driver Code 
$a = 10; $b = 15; 
  
// Function call 
echo "GCD(",$a,", ", $b,") = ", gcd($a, $b); 
?> 

Output

GCD(10, 15) = 5

Time Complexity: log(min(a, b))
Auxiliary Space: O(1)

Modular Arithmetic:

Modular arithmetic is another important topic of mathematics that is used in problem solving, especially in competitive programming. This concept is used often when we deal with very large integers and we are satisfied with the modulo answer (i.e., number % N). The concept of modulo is used to avoid the integer overflow error. On many platforms, the values of N are often kept as 10⁹ + 7 or 998244353. Both of these are large primes and we can fit a large range of numbers.

Some important properties of modulo are given below:

(a % b) % b = a % b
(a^b) % a = 0
(a + b) % m = (a % m) + (b % m)
(a * b) % m = ((a % m) * (b % m)) % m
(a – b) % m = ((a % m) – (b % m) + m) % m
(a / b) % m ≠ ((a % m) / (b % m)) % m

Calculating modular inverse is also an important thing that is widely used in several problems, especially in competitive programming.

Binary Exponentiation:

This is a useful way to calculate the powers of any number i.e., a^b. To do this, we generally multiply ‘a‘ with itself ‘b‘ times. Let us have a look at the following exponent expression:

7⁵ = 7⁴⁺¹ = 7⁴ * 7¹. This we can get by expressing 5 in binary terms i.e., ‘101‘ and considering the powers only for the set bit positions i.e. at first set bit power = 2⁰ = 1 and at second set bit power = 2² = 4.

Note, that any power in the sequence is only the square of the previous number in the sequence:

7² = (7¹)²
7⁴ = (7²)² and so on

Using this idea, we can make use of the binary expression of the exponent and calculate the power efficiently. We have to sequentially keep on calculating the powers of the number and multiply only those with the answer for which the corresponding bit of the exponent is set. As we are working with the binary expression, it takes only O(log(b)) time.

Code implementation of Binary exponentiation:

C++

// C++ code to implement binary exponentiation 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to utilise the binary exponentiation 
int power(int x, int y) 
{ 
    // Initialize answer 
    int res = 1; 
  
    // Check till the number becomes zero 
    while (y > 0) { 
  
        // If y is odd, multiply x with result 
        if (y % 2 == 1) 
            res = (res * x); 
  
        // y = y/2 
        y = y >> 1; 
  
        // Change x to x^2 
        x = (x * x); 
    } 
    return res; 
} 
  
// Driver code 
int main() 
{ 
    int x = 2, y = 5; 
  
    // Function call 
    cout << "Power is " << power(x, y); 
    return 0; 
}

Java

// Java code to implement binary exponentiation 
import java.io.*; 
  
class GFG { 
  
    // Function to utilise the binary exponentiation 
    static int power(int x, int y) 
    { 
        // Initialize result 
        int res = 1; 
  
        // Check till the number becomes zero 
        while (y > 0) { 
  
            // If y is odd, multiply x with result 
            if ((y & 1) != 0) 
                res = res * x; 
  
            // y = y/2 
            y = y >> 1; 
  
            // Change x to x^2 
            x = x * x; 
        } 
        return res; 
    } 
  
    // Driver code 
    public static void main(String[] args) 
    { 
        int x = 2, y = 5; 
  
        // Function call 
        int mod = power(x, y); 
        System.out.print("Power is " + mod); 
    } 
}

Python3

# Python3 code to implement binary exponentiation 
  
  
# Function to utilise the binary exponentiation 
def power(x, y): 
      
    # Initialize result 
    res = 1
  
    # Check till the number becomes zero 
    while (y > 0): 
  
        # If y is odd, multiply x with result 
        if ((y & 1) != 0): 
            res = res * x 
  
        # y = y/2 
        y = y >> 1
          
        # Change x to x^2 
        x = x * x 
  
    return res 
  
  
# Driver Code 
if __name__ == '__main__': 
    x = 2
    y = 5
      
    # Function call 
    print("Power is", power(x, y))

C#

// C# code to implement binary exponentiation 
using System; 
  
class GFG { 
      
    // Function to utilise the binary exponentiation 
    static int power(int x, int y) 
    { 
        // Initialize result 
        int res = 1; 
  
        // Check till the number becomes zero 
        while (y > 0) { 
              
            // If y is odd, multiply x with result 
            if ((y & 1) != 0) 
                res = res * x; 
  
            // y = y/2 
            y = y >> 1; 
            
            // Change x to x^2 
            x = x * x; 
        } 
        return res; 
    } 
  
    // Driver Code 
    static public void Main() 
    { 
        int x = 2, y = 5; 
        
        // Function call 
        Console.Write("Power is " + power(x, y)); 
    } 
}

Javascript

// Javascript code to implement binary exponentiation 
  
  
// Function to utilise the binary exponentiation 
function power(x, y) 
{ 
    // Initialize result 
    let res = 1; 
  
    // Check till the number becomes zero 
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = res*x; 
  
        // y = y/2 
        y = y>>1; 
          
        // Change x to x^2 
        x = x*x; 
    } 
    return res; 
} 
  
// Driver Code 
let x = 2; 
let y = 5; 
  
// Function call 
console.log("Power is " + power(x, y));

Output

Power is 32

Time Complexity: O(log(y))
Auxiliary Space: O(1)

Modular Exponentiation:

Modular exponentiation can be said to be an extension of Binary exponentiation. It is very often used in problem solving to get the exponent within a range that does not cause integer overflow. It is utilised to calculate the exponent modulo to some other prime i.e., (a^b) % p. Modular exponentiation uses the concept of both binary exponentiation and modular arithmetic.

This algorithm uses the concept of binary exponentiation to calculate the power in less time and the formula of modular multiplication as shown in the above section for getting the required value of the exponent.

Code implementation of Modular exponentiation:

C++

// C++ program to compute modular power 
#include <bits/stdc++.h> 
using namespace std; 
  
// Iterative Function to calculate (x^y)%p in O(log y) 
int power(long long x, unsigned int y, int p) 
{ 
    int res = 1; 
  
    // Update x if it is more than or equal to p 
    x = x % p; 
  
    // In case x is divisible by p 
    if (x == 0) 
        return 0; 
  
    while (y > 0) { 
          
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res * x) % p; 
  
        // y = y/2 
        y = y >> 1; 
        x = (x * x) % p; 
    } 
    return res; 
} 
  
// Driver code 
int main() 
{ 
    int x = 2, y = 5, p = 13; 
  
    // Function  call 
    cout << "Power is " << power(x, y, p); 
    return 0; 
}

Java

// Java program to compute modular power 
import java.io.*; 
  
class GFG { 
  
    // Iterative Function to calculate (x^y) in O(log y) 
    static int power(int x, int y, int p) 
    { 
        int res = 1; 
  
        // Update x if it is more than or equal to p 
        x = x % p; 
  
        // In case x is divisible by p 
        if (x == 0) 
            return 0; 
  
        while (y > 0) { 
              
            // If y is odd, multiply x with result 
            if ((y & 1) != 0) 
                res = (res * x) % p; 
  
            // y = y/2 
            y = y >> 1; 
            x = (x * x) % p; 
        } 
        return res; 
    } 
  
    // Driver Code 
    public static void main(String[] args) 
    { 
        int x = 2, y = 5, p = 13; 
  
        // Function call 
        System.out.print("Power is " + power(x, y, p)); 
    } 
}

Python3

# Python3 program to compute modular power 
  
  
# Iterative Function to calculate (x^y)%p in O(log y) 
def power(x, y, p): 
  
    # Initialize result 
    res = 1
  
    # Update x if it is more than or equal to p 
    x = x % p 
  
    # In case x is divisible by p; 
    if (x == 0): 
        return 0
  
    while (y > 0): 
        # If y is odd, multiply x with result 
        if ((y & 1) == 1): 
            res = (res * x) % p 
  
        # y = y/2 
        y = y >> 1
        x = (x * x) % p 
  
    return res 
  
  
# Driver Code 
if __name__ == '__main__': 
    x = 2
    y = 5
    p = 13
  
    # Function call 
    print("Power is", power(x, y, p)) 

C#

// C# program to compute modular power 
using System; 
  
public class GFG { 
  
    // Iterative Function to calculate (x^y) in O(log y) 
    static int power(int x, int y, int p) 
    { 
        int res = 1; 
  
        // Update x if it is more than or equal to p 
        x = x % p; 
  
        // In case x is divisible by p 
        if (x == 0) 
            return 0; 
  
        while (y > 0) { 
            
            // If y is odd, multiply x with result 
            if ((y & 1) != 0) 
                res = (res * x) % p; 
  
            // y = y/2 
            y = y >> 1; 
            x = (x * x) % p; 
        } 
        return res; 
    } 
  
    // Driver Code 
    static public void Main() 
    { 
        int x = 2, y = 5, p = 13; 
  
        // Function call 
        Console.Write("Power is " + power(x, y, p)); 
    } 
}

Javascript

// Javascript program to compute modular power 
  
// Iterative Function to calculate (x^y)%p in O(log y) 
function power(x, y, p) 
{ 
    let res = 1; 
  
    // Update x if it is more than or equal to p 
    x = x % p; 
  
    // In case x is divisible by p 
    if (x == 0) 
        return 0; 
  
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res * x) % p; 
  
        // y = y/2 
        y = y >> 1; 
        x = (x * x) % p; 
    } 
    return res; 
} 
  
// Driver Code 
let x = 2; 
let y = 5; 
let p = 13; 
  
// Function call 
console.log("Power is " + power(x, y, p));

PHP

<?php 
// PHP program to compute modular power 
  
// Iterative Function to calculate (x^y)%p in O(log y) 
function power($x, $y, $p) 
{ 
    $res = 1; 
  
    // Update x if it is more than or equal to p 
    $x = $x % $p; 
  
    // In case x is divisible by p 
    if ($x == 0) 
        return 0; 
  
    while ($y > 0) 
    { 
        // If y is odd, multiply x with result 
        if ($y & 1) 
            $res = ($res * $x) % $p; 
  
        // y = $y/2 
        $y = $y >> 1; 
        $x = ($x * $x) % $p; 
    } 
    return $res; 
} 
  
// Driver Code 
$x = 2; 
$y = 5; 
$p = 13; 
  
// Function call 
echo "Power is ", power($x, $y, $p); 
?> 

Output

Power is 6

Time Complexity: O(log(y))
Auxiliary Space: O(1)

Sieve of Eratosthenes:

This is one of the most used mathematical algorithms. The Sieve of Eratosthenes is used to find all the prime numbers upto any value N. Though there is another way to find the primes by iterating all numbers till N and checking each of them, that is not efficient. It takes time of O(N*sqrt(N)) time, whereas, using the Sieve of Eratosthenes, we can find the primes in O(N*log(logN)) time.

The idea behind this algorithm is that, any non-prime number is divisible by at least one prime below that number. Inversely we can say that a number is prime if none of the smaller prime divides it.

So, to find the prime we traverse from the smallest prime (i.e., 2) to sqrt(N) and mark all its multiple which are greater than or equal to its square as non-prime [We start from square because the smaller ones are multiple of some smaller prime also and will be visited then].

Code implementation of Sieve of Eratosthenes:

C++

// C++ program to print all primes smaller than 
// or equal to n using Sieve of Eratosthenes 
#include <bits/stdc++.h> 
using namespace std; 
  
void SieveOfEratosthenes(int n) 
{ 
    // Create a boolean array "prime[0..n]" and 
    // initialize all entries as true. 
    // A value in prime[i] will finally be false 
    // if i is Not a prime, else true. 
    bool prime[n + 1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p = 2; p * p <= n; p++) { 
  
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) { 
  
            // Update all multiples of p greater than or 
            // equal to the square of it numbers 
            // which are multiple of p and are less than p^2 
            // have already been marked. 
            for (int i = p * p; i <= n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p = 2; p <= n; p++) 
        if (prime[p]) 
            cout << p << " "; 
} 
  
// Driver Code 
int main() 
{ 
    int n = 30; 
    cout << "Following are the prime numbers smaller "
         << "than or equal to " << n << endl; 
  
    // Function call 
    SieveOfEratosthenes(n); 
    return 0; 
}

Java

// Java program to print all primes smaller than 
// or equal to n using Sieve of Eratosthenes 
import java.io.*; 
  
class SieveOfEratosthenes { 
    void sieveOfEratosthenes(int n) 
    { 
        // Create a boolean array "prime[0..n]" and 
        // initialize all entries it as true. 
        // A value in prime[i] will finally be false 
        // if i is Not a prime, else true. 
        boolean prime[] = new boolean[n + 1]; 
        for (int i = 0; i <= n; i++) 
            prime[i] = true; 
  
        for (int p = 2; p * p <= n; p++) { 
  
            // If prime[p] is not changed, 
            // then it is a prime 
            if (prime[p] == true) { 
  
                // Update all multiples of p greater than or 
                // equal to the square of it numbers which 
                // are multiple of p and are less than p^2 
                // are already been marked. 
                for (int i = p * p; i <= n; i += p) 
                    prime[i] = false; 
            } 
        } 
  
        // Print all prime numbers 
        for (int i = 2; i <= n; i++) { 
            if (prime[i] == true) 
                System.out.print(i + " "); 
        } 
    } 
  
    // Driver Code 
    public static void main(String args[]) 
    { 
        int n = 30; 
        SieveOfEratosthenes g = new SieveOfEratosthenes(); 
        System.out.println( 
            "Following are the prime numbers "
            + "smaller than or equal to " + n); 
        
        // Function call 
        g.sieveOfEratosthenes(n); 
    } 
}

Python3

# Python program to print all primes smaller than 
# or equal to n using Sieve of Eratosthenes 
  
  
def SieveOfEratosthenes(n): 
  
    # Create a boolean array "prime[0..n]" and 
    # initialize all entries as true. 
    # A value in prime[i] will finally be false 
    # if i is Not a prime, else true. 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
  
        # If prime[p] is not changed, then it is a prime 
        if (prime[p] == True): 
  
            # Update all multiples of p 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
  
    # Print all prime numbers 
    for p in range(2, n+1): 
        if prime[p]: 
            print(p, end=" ") 
  
  
# Driver code 
if __name__ == '__main__': 
    n = 30
    print("Following are the prime numbers" \ 
    " smaller than or equal to", n) 
  
    # Function call 
    SieveOfEratosthenes(n) 

C#

// C# program to print all primes smaller than 
// or equal to n using Sieve of Eratosthenes 
using System; 
  
public class GFG { 
  
    public static void SieveOfEratosthenes(int n) 
    { 
        // Create a boolean array "prime[0..n]" and 
        // initialize all entries as true. 
        // A value in prime[i] will finally be false 
        // if i is Not a prime, else true. 
        bool[] prime = new bool[n + 1]; 
  
        for (int i = 0; i <= n; i++) 
            prime[i] = true; 
  
        for (int p = 2; p * p <= n; p++) { 
            // If prime[p] is not changed, 
            // then it is a prime 
            if (prime[p] == true) { 
                // Update all multiples of p 
                for (int i = p * p; i <= n; i += p) 
                    prime[i] = false; 
            } 
        } 
  
        // Print all prime numbers 
        for (int i = 2; i <= n; i++) { 
            if (prime[i] == true) 
                Console.Write(i + " "); 
        } 
    } 
  
    // Driver Code 
    public static void Main() 
    { 
        int n = 30; 
        Console.WriteLine("Following are the prime numbers"
                      + " smaller than or equal to " + n); 
  
        // Function call 
        SieveOfEratosthenes(n); 
    } 
}

Javascript

// javascript program to print all primes smaller than 
// or equal to n using Sieve of Eratosthenes 
  
  
function sieveOfEratosthenes(n) 
{ 
    // Create a boolean array "prime[0..n]" and 
    // initialize all entries as true. 
    // A value in prime[i] will finally be false 
    // if i is Not a prime, else true. 
    prime = Array.from({length: n+1}, (_, i) => true); 
  
    for (p = 2; p * p <= n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p 
            for (i = p * p; i <= n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (i = 2; i <= n; i++) 
    { 
        if (prime[i] == true) 
            console.log(i + " "); 
    } 
} 
  
// Driver Code 
var n = 30; 
console.log( 
    "Following are the prime numbers "
    + "smaller than or equal to " + n); 
  
// Function call 
sieveOfEratosthenes(n);

C

// C program to print all primes smaller than 
// or equal to n using Sieve of Eratosthenes 
#include <stdbool.h> 
#include <stdio.h> 
#include <string.h> 
  
void SieveOfEratosthenes(int n) 
{ 
    // Create a boolean array "prime[0..n]" and  
    // initialize all entries as true. 
    // A value in prime[i] will finally be false 
    // if i is Not a prime, else true. 
    bool prime[n + 1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p = 2; p * p <= n; p++) { 
  
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) { 
  
            // Update all multiples of p greater than or 
            // equal to the square of it numbers 
            // which are multiple of p and are less than p^2 
            // have already been marked. 
            for (int i = p * p; i <= n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p = 2; p <= n; p++) 
        if (prime[p]) 
            printf("%d ", p); 
} 
  
// Driver Code 
int main() 
{ 
    int n = 30; 
    printf("Following are the prime numbers smaller than "
           "or equal to %d \n", 
           n); 
  
    // Function call 
    SieveOfEratosthenes(n); 
    return 0; 
}

PHP

<?php 
// php program to print all primes smaller than or 
// equal to n using Sieve of Eratosthenes 
  
function SieveOfEratosthenes($n) 
{ 
    // Create a boolean array "prime[0..n]" 
    // and initialize all entries it as true. 
    // A value in prime[i] will finally be 
    // false if i is Not a prime, else true. 
    $prime = array_fill(0, $n+1, true); 
  
    for ($p = 2; $p*$p <= $n; $p++) 
    {     
        // If prime[p] is not changed, 
        // then it is a prime 
        if ($prime[$p] == true) 
        {         
            // Update all multiples of p 
            for ($i = $p*$p; $i <= $n; $i += $p) 
                $prime[$i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for ($p = 2; $p <= $n; $p++) 
        if ($prime[$p]) 
            echo $p." "; 
} 
  
// Driver Code 
    $n = 30; 
    echo "Following are the prime numbers "
    ."smaller than or equal to " .$n."\n" ; 
     
    // Function call 
    SieveOfEratosthenes($n); 
?> 

Output

Following are the prime numbers smaller than or equal to 30 
2 3 5 7 11 13 17 19 23 29

Time Complexity: O(log(log n))
Auxiliary Space: O(N)

Other useful Mathematical Concepts for Competitive Programming:

The above mentioned algorithms are some of the most important algorithms and concepts. Apart from these, there are also some general mathematical concepts that come in handy while we are practicing programming or participating in competitive programming. Those are mentioned below:

GCD and LCM:

GCD and LCM are two of the most common mathematical concepts. GCD or Greatest Common Divisor is also known as HCF or Highest Common Factor. As the name suggests, GCD of two numbers is the highest number which is a factor of both numbers.

On the other hand, LCM or Least Common multiple of any two numbers is the lowest number which is also a multiple of both values in question. There is an important relation between GCD and LCM which is GCD*LCM = multiplication of both numbers.

To solve questions based on GCD and LCM, refer to this page.

Number System:

The number system is another important concept for mathematical algorithms and solving other problems. The number system deals with the representation of numbers in different bases. Some of the most commonly used number systems are the Decimal number system, Binary System, Hexadecimal number system, etc. Converting one number system to another is also an important aspect like Binary to Decimal, Decimal to Hexadecimal, Decimal to Binary, etc.

Prime Numbers:

By definition, prime numbers are those positive numbers that have only two factors, 1 and the number itself. It is important in both mathematics and computer science and used in several cases like prime factorization, modulo operations, in cryptography, etc. The Sieve of Eratosthenes algorithm mentioned above also deals with prime numbers.

Primality Testing is also associated with prime numbers. The method for determining whether a number is prime or not is called primality testing. To learn more about the topics, refer to this page.

Permutation and Combination:

Permutation and combination are some of the widely used topics in mathematics. It also has wide application in computer science. Permutation is defined as the number of ways of arranging a number of elements.

On the other hand, the combination is defined as the number of ways of selecting some number of elements from the given number of items. One of the several usages of permutation and combination is the Catalan number.

Set theory:

A set is defined as a structured collection of distinct elements. It is a core concept of mathematics. The concept of set is the underlying idea of Set Data Structure. Whenever we need the distinct elements from a collection of items the concept of set is utilised. Subset sum problem, power set are some of the problems where the idea of set theory is used.

What are Geometric Algorithms?

In different areas of computer science such as robotics, data analysis, computer graphics, virtual reality and etc we need to deal with the geometric aspect or spatial data. The algorithms devised to deal with these types of data are known as geometric algorithms.

Some use cases of Geometric Algorithms:

1. Data mining: It is very much useful in data mining. Finding the relations between two points are based on the usage of geometric algorithms.

2. Simulation: For simulations of real-life objects we need to understand their geometry and reflect it properly. This is the aspect where geometric algorithms come in handy.

3. Virtual Reality: The usage of these algorithms can be experienced in virtual reality. How to transfer the points and their relative spacing requires the usage of these algorithms.

Some important Geometric Algorithms and Concepts:

Pattern Printing:

To understand the basic working of loops, a newcomer goes through pattern printing. Printing several patterns require knowledge of the geometric shape of those and how an algorithm can be devised to print those patterns on the screen of computer. Some common patterns are provided here for your practice.

Convex Hull:

Perhaps the most important geometric concept is the Convex Hull. The statement for the problem is as follows:

Given a set of points. The Convex Hull of the set is the smallest convex polygon that contains all the points in it.

There are various ways to solve the problem:

Convex Hull using Jarvis Algorithm: The idea of this algorithm is very simple. We start from the leftmost point (the point with the least x coordinate value) and start wrapping the other points in a counterclockwise manner. Here the problem is to find the next point in a counterclockwise direction from a given point. The idea is to use orientation here.

Convex Hull using Divide and Conquer: This algorithm uses the idea that if we know the left convex hull and the right convex hull, we can get the final convex hull of all the points. This is obtained by adding the upper tangent and the lower tangent of the convex hulls. So for this, the prerequisite is to know the algorithm for tangent between two convex polygons.

Convex Hull using Graham Scan: This algorithm works by using the concept of polar angle. In this algorithm, initially the bottom-most point is found and the remaining points are sorted as per their polar angle in counterclockwise manner. Then the points are processed with the help of a stack and their orientation. This takes the time complexity of O(N * logN) where N is the number of points.

Monotone Chain Algorithm for Convex Hull: To apply this algorithm the points are first sorted based on their ‘x‘ coordinates. The algorithm works by finding upper and lower Hull. The leftmost among the sorted points is found and rotate is clockwise direction to find the next point and repeat this till the rightmost point is reached. After then again rotate clockwise to find the lower Hull.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!

Last Updated : 25 Aug, 2023