Euler's totient function for large numbers

Question

I made this algorithm to compute Euler's totient function for large numbers. A sieve is used.

#include <iostream>
#include <cstdint>
#include <vector>
typedef uint64_t integer;
integer euler_totient(integer n) {
 integer L1_CACHE = 32768;
 integer phi_n=0;
 if (n>0) {
 phi_n++; 
 integer segment_size=std::min(L1_CACHE,n);
 std::vector<char> SIEVE(segment_size, true);
 std::vector<integer> PRIME;
 integer len_PRIME=0;
 for (integer p=2; p<segment_size; p++)
 if (SIEVE[p]==true)
 if (n%p==0) {
 for (integer m=p; m<segment_size; m+=p)
 SIEVE[m]=false;
 PRIME.push_back(p);
 len_PRIME++;
 }
 else
 phi_n++;
 if (n>segment_size) {
 integer m,p;
 for (integer segment_low=segment_size; segment_low<n; segment_low+=segment_size) {
 std::fill(SIEVE.begin(), SIEVE.end(), true);
 for (integer i=0; i<len_PRIME; i++) {
 m=(PRIME[i]-segment_low%PRIME[i])%PRIME[i];
 for(;m<segment_size;m+=PRIME[i])
 SIEVE[m]=false;
 }
 for (integer i=0; i<segment_size && segment_low+i<n; i++)
 if (SIEVE[i]==true){
 p=segment_low+i;
 if (n%p==0) {
 for (m=i; m<segment_size; m+=p)
 SIEVE[m]=false;
 PRIME.push_back(p);
 len_PRIME++;
 }
 else
 phi_n++;
 }
 }
 } 
 } 
 return phi_n;
}
int main() {
 std::cout << euler_totient(1000000) << std::endl;
 return 0;
}

Is it a good solution?

Can it be improved in any way?

• vnp: Unfortunately, it gives plenty of incorrect results (eg for 6 it gives 3 instead of 2, for 14 it gives 7 instead of 5, etc). You need better testing. VTC.
• user140242: @vnp I reverted to the original version by making a fix. But phi (14)=6.

Answer 1

Is it a good solution?

Unfortunately I'll have to go with "not really".

This approach can be summarized as taking the definition of the totient of n as "the number of positive integers up to n that are relatively prime to n" literally, turning it into an algorithm.

This approach does not take advantage of any factors that are found. What I mean by that is, for example, if n = 2^k, then an algorithm based on factorization will find the totient almost immediately, while this algorithm will still have to iterate up to n. Or, imagine you discover that n is divisible by 1009 (and only once, meaning that n is not divisible by 10092 - you can easily deal with prime powers, but I didn't want to do it for the example), then you would know that totient(n) = 1008 * totient(n / 1009). If you were going to iterate up to n (which is not necessary) then this would effectively cut the remaining amount of iteration by a factor of 1009.

Also not finding factors is useful: when n is a prime, that is a fact that can be discovered more quickly than iterating all the way up to n (doing it naively, discovering that n is prime would happen after sqrt(n) steps, significantly better than n), and then the totient is just n - 1.

The simplest factorization-based approach, which just uses trial division, nothing fancy, would only need to count up to sqrt(n), and only in the worst case, when n is prime. Otherwise, factors are found along the way and every time one of them is found, the bound up to which the trial division needs to go is significantly reduced.

To show how big the difference could be, let's take the totient of 2364968846596223957 (I got this by drawing a random 64bit number). Using a simple trial-division based computation that I quickly worked out, nothing special, my PC took 80 milliseconds to compute the result 2360645320368442380 (which is correct, verified with WolframAlpha). Counting up to that number would take years.

---

In terms of coding style, I have a couple of remarks as well. There is very little white space, such as around operators and also sometimes between the different "parts" in a for statement. Styles differ, but I don't find this nice to read. It's very visually dense. Also, there is a repeated use of if or for with non-trivial contents, yet without braces. That is commonly recommended against in style guides (sometimes recommendations even go so far as to always demand braces, even if the contents are trivial) and personally I also recommend against it. I also find typedef uint64_t integer questionable, what do you gain from this?

• user140242: I'm not an expert pogrammer and I wrote the code quickly. I was more interested in the opinion of the algorithm. Thank you.
• Toby Speight: The typedef is particularly problematic since there are two reasons that uint64_t may be undefined (<cstdint> will only provide std::uint64_t if an exactly-64-bit type is available, and it isn't guaranteed to declare the global-namespace version). I'd recommend using std::uint_fast64_t instead.