Тотиентното решето е алгоритъм, за намирането на всички стойности на функцията на Ойлер, φ(x) за x=1..n.
Алгоритъм Идеята на алгоритъма е, че ако дадено число x, се дели на по-малко от него y, то x задължително не е взаимно просто и с всяко друго кратно на y.
Алгоритъмът е разширение на решетото на Ератостен: той също така намира и простите числа в интервала (1;n].
Описание Стъпките за създаване и попълване на тотиентното решето са следните: Съставяме списък на всички числа от 1 до n и под всяко пишем неговата стойност. Започвайки от две изреждаме всяко число и изпълняваме: Ако числото е със стойност различна от номера си, продължаваме към следващото Ако числото 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.
Категория:Теория на числата Категория:Алгоритми