Тотиентно решето

Тотиентното решето е алгоритъм, за намирането на всички стойности на функцията на Ойлер, φ(x) за x=1..n.

Алгоритъм

Идеята на алгоритъма е, че ако дадено число x, се дели на по-малко от него y, то x задължително не е взаимно просто и с всяко друго кратно на y.

Алгоритъмът е разширение на решетото на Ератостен: той също така намира и простите числа в интервала (1;n].

Описание

Стъпките за създаване и попълване на тотиентното решето са следните:

1. Съставяме списък на всички числа от 1 до n и под всяко пишем неговата стойност.
2. Започвайки от две изреждаме всяко число и изпълняваме:
   1. Ако числото е със стойност различна от номера си, продължаваме към следващото
   2. Ако числото x е със стойност равна на номера си (значи е просто), за него и всяко x-то, вадим частното (без да взимаме предвид остатъка) от деленето на текущата стойност на x-тото число с x.

След изпълняване на алгоритъма за всички числа до n, за всяко ще имаме стойността на φ(x)

Псевдокод

да се попълни масива Phi, така че Phi[i]=i;
за всяко i = 2 до n
   ако Phi[i] == i, тогава //i е просто
   j = i;
   докато j <= n
      Phi[j] = Phi[j] - Phi[j]/i;
      j = j + i;

След изпълняване на алгоритъма, Phi[i], ще е равно на φ(i), за всяко i=1..n.