Return to Question

#include <iostream>
#include <cstdint>
#include <vector>
#include <cmath> 

typedef uint64_t integer;

integer euler_totient(integer n) {
 integer phi_n=n;
 integer len_SIEVE=(integer) std::sqrt(n)+1;
 std::vector<char> SIEVE(len_SIEVE, true); 
 for (integer p=2; p<len_SIEVE; p++)
 if (SIEVE[p]==true)
 if (n%p==0) {
 for (integer m=p; m<len_SIEVE; m+=p)
 SIEVE[m]=false;
 phi_n/=p;
 phi_n*=p-1;
 }
 if (phi_n==n)
 phi_n--;
 return phi_n;
}
int main() {
 std::cout << euler_totient(100000000) << std::endl;
 return 0;
}

Can it be improved in any way?

EDIT: I ​​changed the algorithm because I realized that the second part was useless.

#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;
}

Can it be improved in any way?

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

#include <iostream> 
#include <cstdint> 
#include <vector> 
#include <cmath> 
 
typedef uint64_t integer; 
 
integer euler_totient(integer n) { 
 integer phi_n=n;
 integer len_SIEVE=(integer) std::sqrt(n)+1;
 std::vector<char> SIEVE(len_SIEVE, true); 
 for (integer p=2; p<len_SIEVE; p++) 
 if (SIEVE[p]==true) 
 if (n%p==0) {
 for (integer m=p; m<len_SIEVE; m+=p) 
 SIEVE[m]=false;
 phi_n/=p;
 phi_n*=p-1;
 }
 return phi_n; 
}
int main() {
 std::cout << euler_totient(100000000) << std::endl;
 return 0;
}

Is it a good solution?

Can it be improved in any way?

EDIT: I ​​changed the algorithm because I realized that the second part was useless.

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

#include <iostream> 
#include <cstdint> 
#include <vector> 
#include <cmath> 
 
typedef uint64_t integer; 
 
integer euler_totient(integer n) { 
 integer phi_n=n;
 integer len_SIEVE=(integer) std::sqrt(n)+1;
 std::vector<char> SIEVE(len_SIEVE, true); 
 for (integer p=2; p<len_SIEVE; p++) 
 if (SIEVE[p]==true) 
 if (n%p==0) {
 for (integer m=p; m<len_SIEVE; m+=p) 
 SIEVE[m]=false;
 phi_n/=p;
 phi_n*=p-1;
 }
 if (phi_n==n)
 phi_n--;
 return phi_n; 
}
int main() {
 std::cout << euler_totient(100000000) << std::endl;
 return 0;
}

Is it a good solution?

Can it be improved in any way?

EDIT: I ​​changed the algorithm because I realized that the second part was useless.

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

#include <iostream>
#include <cstdint>
#include <vector>
#include <cmath>
#include <algorithm>
typedef uint64_t integer;
integer euler_totient(integer n) {
 integer phi_n=1;
 integer segment_size=(integer) std::sqrt(n)+1;
 segment_size=std::max(segment_size,(integer) 1024);
 std::vector<char> SIEVE(segment_size, true); std::vector<integer> PRIME;
 for (integer p=2; p<segment_size && p<n; 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);
  }
 else
 phi_n++;
 if (n>=segment_size) {
 integer len_PRIME=PRIME.size();
 integer m;
 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)
 phi_n++;
 }
 }
 return phi_n;
}
int main() {
 std::cout << euler_totient(100000000) << std::endl;
 return 0;
}

Is it a good solution?

Can it be improved in any way?

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

#include <iostream>
#include <cstdint>
#include <vector>
#include <cmath> 

typedef uint64_t integer;

integer euler_totient(integer n) {
 integer phi_n=n;
 integer len_SIEVE=(integer) std::sqrt(n)+1;
 std::vector<char> SIEVE(len_SIEVE, true); 
 for (integer p=2; p<len_SIEVE; p++)
 if (SIEVE[p]==true)
 if (n%p==0) {
 for (integer m=p; m<len_SIEVE; m+=p) 
 SIEVE[m]=false;
 phi_n/=p;
 phi_n*=p-1;
 }
 return phi_n;
}
int main() {
 std::cout << euler_totient(100000000) << std::endl;
 return 0;
}

Is it a good solution?

Can it be improved in any way?

EDIT: I ​​changed the algorithm because I realized that the second part was useless.