Over a million developers have joined DZone.

Euler's Phi Function.

DZone's Guide to

Euler's Phi Function.

Free Resource
Returns the value of Euler's phi function for n. It basically calculates the number of relative prime integers to n smaller than n.

This only works if there the prime numbers smaller than n are stored in the array prime[] of nrPrime elements.

You can use this function to generate them:

int phi(int n) {
  double rez = n;

  int i = 0;
  while ((i < nrPrime) && (prime[i] <= n)) {
    if (n % prime[i] == 0) {
      rez *= (double)(prime[i] - 1) / (double)prime[i];

  return rez;


Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}