4141. Euler Totient Function

 

In number theory, the totient φ of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n.

Given an integer n (1 ≤ n ≤ 106). Compute the value of the totient φ.

 

Input. First line contains the number of test cases t (t ≤ 20000). Each of the following t lines contains an integer n.

 

Output. t lines, one for the result of each test case.

 

Sample Input

Sample Output

5

1

2

3

4

5

1

1

2

2

4

 

 

РЕШЕНИЕ

Функция Эйлера

 

Анализ алгоритма

Реализуем решето, которое вычислит все значения функции Эйлера от 1 до 106 и занесет их в массив fi. Далее для каждого входного значения n выведем fi[n].

 

Реализация алгоритма

 

#include <stdio.h>

#include <string.h>

#define MAX 1000010

 

int  fi[MAX];

 

void FillEuler(void)

{

  int i, j;

  memset(fi,0,sizeof(fi)); fi[1] = 1;

  for(i = 2; i < MAX; i++)

    if(!fi[i])

      for(j = i; j < MAX; j += i)

      {

        if(!fi[j]) fi[j] = j;

        fi[j] -= fi[j]/i;

      }

}

 

int tests, n;

 

int main(void)

{

  FillEuler();

  scanf("%d",&tests);

  while(tests--)

  {

    scanf("%d",&n);

    printf("%d\n",fi[n]);

  }

  return 0;

}