Otherwise, we can build a for loop to find positive integer numbers that co-prime to it but this requires O(n) complexity. In that way, we can find the phi with O(1) complexity. Instead of counting positive integer numbers that co-prime to it, we can find the multiplication of its multipliers’s totient function results. Herein, totient function is a multiplicative function. Even though, n is a prime number, it is the multiplication of two prime numbers. However, we picked the n as the multiplication of two prime numbers.
We know that if n is a prime number, then positive integer number that co-prime to it should be (n-1). Totient function of n counts the positive integer numbers that co-prime to n. These variables are coming from the Euler’s generalization of Fermat’s Little Theorem. Then, we will find the module n and totient n (or shortly phi) variables from p and q. If you set a non-prime number to p or q, then this program will raise an error. A prime number must not be divided by another number less than it without remainder. To have a safety net, we should check the primeness of this p and q pair. In a practical application, these should be large primes but we will use small ones in this example.
The algorithm expects to pick two prime numbers first.
