Eulers Function Algorithm

Euler's Function Algorithm, also known as the Euler's Totient Function, is a powerful number-theoretic concept developed by the Swiss mathematician Leonhard Euler. The algorithm calculates φ(n), which represents the number of positive integers less than or equal to 'n' that are relatively prime to 'n,' i.e., the integers that have no common divisors with 'n' other than one. The primary application of this function is in number theory and cryptography, particularly in the RSA encryption algorithm, where it is used to determine the strength of cryptographic keys and maintain secure communication. The algorithm follows some essential properties, such as multiplicativity, which states that if two numbers are coprime, then the Euler's totient function of their product is the product of their individual Euler's totient functions. Additionally, Euler's theorem states that if 'a' and 'n' are coprime positive integers, then a raised to the power of φ(n) is congruent to 1 modulo n, i.e., a^φ(n) ≡ 1 (mod n). This theorem is a generalization of Fermat's Little Theorem and serves as the foundation for many important results in number theory and cryptography.
package Others;

/**
 * You can read more about Euler's totient function
 * <p>
 * See https://en.wikipedia.org/wiki/Euler%27s_totient_function
 */
public class EulersFunction {
    // This method returns us number of x that (x < n) and gcd(x, n) == 1 in O(sqrt(n)) time complexity;
    public static int getEuler(int n) {
        int result = n;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                while (n % i == 0) n /= i;
                result -= result / i;
            }
        }
        if (n > 1) result -= result / n;
        return result;
    }

    public static void main(String[] args) {
        for (int i = 1; i < 100; i++) {
            System.out.println(getEuler(i));
        }
    }
}

LANGUAGE:

DARK MODE: