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?
6
it gives3
instead of2
, for14
it gives7
instead of5
, etc). You need better testing. VTC. \$\endgroup\$