10) Euler Totient Function
Euler’s Totient Function, denoted as ϕ(n), gives the count of positive integers less than or equal to n that are relatively prime to n.
Formula:
Below is the code snippet for Euler Totient Function:
#include <iostream>
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);
}
// A simple method to evaluate Euler Totient Function
int phi(unsigned int n) {
unsigned int result = 1; // Start with 1 because gcd(1, n) is always 1
for (int i = 2; i < n; i++) {
if (gcd(i, n) == 1) {
result++; // Increment result for every i that is coprime with n
}
}
return result;
}
// Example usage
int main() {
unsigned int n = 10; // Example value
cout << "Euler's Totient Function for " << n << " is " << phi(n) << endl;
return 0;
}
import java.util.Scanner;
public class EulerTotientFunction {
// 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);
}
// A simple method to evaluate Euler Totient Function
public static int phi(int n) {
int result = 1; // Start with 1 because gcd(1, n) is always 1
for (int i = 2; i < n; i++) {
if (gcd(i, n) == 1) {
result++; // Increment result for every i that is coprime with n
}
}
return result;
}
// Example usage
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = 10;
System.out.println("Euler's Totient Function for " + n + " is " + phi(n));
scanner.close();
}
}
# Function to return gcd of a and b
def gcd(a, b):
if a == 0:
return b
return gcd(b % a, a)
# A simple method to evaluate Euler Totient Function
def phi(n):
result = 1
for i in range(2, n):
if gcd(i, n) == 1:
result += 1
return result
# Example usage
def main():
n = 10
print("Euler's Totient Function for", n, "is", phi(n))
# Call the main function to execute the example usage
main()
// Function to return gcd of a and b
function gcd(a, b) {
if (a === 0)
return b;
return gcd(b % a, a);
}
// A simple method to evaluate Euler Totient Function
function phi(n) {
let result = 1;
for (let i = 2; i < n; i++) {
if (gcd(i, n) === 1) {
result++;
}
}
return result;
}
// Example usage
function main() {
let n = 10;
console.log("Euler's Totient Function for", n, "is", phi(n));
}
// Call the main function to execute the example usage
main();
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)