Calculation of the Euler function
int phi (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;
}
I have seen the above implementation of the Eiler phi function which is O (sqrt n) . I do not understand the fact of using i*i<=n
in for
and the need for change n
. They say that this can be done in much less O (sqrt n) How? link (in Russian)
source to share
i*i<=n
matches i<= sqrt(n)
from which your iteration only continues up to order sqrt(n)
.
Using the direct definition of the Euler totient function , you must find the prime numbers that divide n
.
source to share
The function is a direct implementation of trial division integer factorization, except that instead of reporting the factors when they find them, the function uses the factors to compute phi. Calculating phi can be done in less than O (sqrt n) using a better algorithm for finding factors; the best way to do this depends on the value of n.
source to share
If the largest number (N say) you need is small enough to have a table of size N in the table, then you can do much better, for an estimate, at the cost of creating a table before any estimates.
One approach would be to first create a table of primes, and then instead of using trial division with every integer no greater than sqrt (n), use trial division with every integer no greater than sqrt (n).
You can improve this by constructing, instead of a prime table, a table that gives (for each integer 2..N) the smallest dividing number. To build such a table, you can use a simple modification of the usual Sieve of Eratosthenes . Then, to calculate the total of a number, you use a table to find the smallest number that divides the number (and accumulates that for you), then divide the number by the entry in the table using the table to find the smallest number that divides it, etc.
source to share