Algebra - RahulKushwaha/Algorithms GitHub Wiki

Greatest Common Divisor:

int GCD(int a, int b){
	if(a == 0){
		return b;
	}

	return GCD(b % a, a);
}

Lowest Common Multiple:

int simpleLCM(int a, int b){
    return (a * b) / GCD(a, b);
}
    
int LCM(int a, int b, int c){
    return simpleLCM(a, simpleLCM(b, c));
}

Euler Totient Function:

phi(n) = It tells us the count of numbers from 1 to n, including n, which are relatively prime to n.

Two numbers, a & b, are called relatively prime if GCD(a, b) = 1;

Method 1: We can iterate over all the numbers from 1 to n and calculate the for each number if the GCD is 1.

int result = 0;
for(int i = 1; i <= n; i ++){
	if(GCD(i, n) == 1){
		result ++;
	}
}

** Total number of bits present in a number is equal to log2(n). Similarly, total number of digits in the number, radix 10, will be log10(n)

Time Complexity: O(n * numberOfDigits(n)) = O(n log10(n))

Each call to the GCD funtion takes O(log10(n)).

Method 2:

int result = n;
int limit = sqrt(n);
for(int i = 2; i <= limit; i ++){
	/*
	Here we are checking if i, the prime number, divides n.
	It is not explicit that i is prime in this case and it is not,
	but if we look closer in the loop, it is evident that when we 
	start with i = 2 and keep on dividing the number n with i until
	n is no more divisible by i. What happens as a result is that other
	multiples of i will not be able to divide the number. 
	For example: n = 24. When i = 2 and we keep on dividing 8 by 2 until
	it is not more divisible then it is not possible for the remaining
	number, 3, to be divisible by 4 or 8.  
	*/
	if(n % i){
		while(n % i == 0){
			n /= i;
			result = (result / i) * (i - 1);
		}
	}
}

// This is only possible if the number if prime
if(n > 1){
	result = n - 1;
}