eulers totient Algorithm
Euler's Totient Algorithm, also known as Euler's Totient Function, is a mathematical algorithm that calculates the number of positive integers less than or equal to a given integer n that are relatively prime to n. In other words, it computes the count of numbers that share no common factors with the given number, except for 1. The function is named after the Swiss mathematician Leonhard Euler, who introduced it in the 18th century. It is denoted by φ(n) or ϕ(n) and plays a critical role in number theory, cryptographic systems, and the study of multiplicative functions.
The algorithm for calculating Euler's Totient Function is based on the property that the function is multiplicative, meaning that if two numbers are coprime (have no common factors other than 1), then the function of their product is the product of their individual functions. The algorithm involves factoring the given number into its distinct prime factors and applying the formula φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk), where p1, p2, ..., pk are the distinct prime factors of n. For example, φ(12) would be calculated as 12 * (1 - 1/2) * (1 - 1/3) = 12 * (1/2) * (2/3) = 4, since the prime factors of 12 are 2 and 3. This algorithm allows for efficient computation of the Euler's Totient Function, which is essential in various applications, such as the RSA encryption algorithm.
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
return (b > 0 ? gcd(b, a%b) : a);
}
unsigned int phi(unsigned int n)
{
unsigned int result = 1;
for (int i = 2; i < n; ++i)
{
if (gcd(i, n) == 1)
{
result++;
}
}
return result;
}
int main()
{
int n;
cin >> n;
assert(n <= 1000000); // Assertion to ensure execution time is reasonable ( < 1second)
cout << "Value of Euler's totient function for n is " << phi(n) << endl;
return 0;
}
