Тотиентно решето
 | За информацията в тази статия или раздел не са посочени източници. Въпросната информация може да е непълна, неточна или изцяло невярна. Имайте предвид, че това може да стане причина за изтриването на цялата статия или раздел. Шаблонът е поставен на 12:56, 9 ноември 2016 (UTC). |  |
Тотиентното решето е алгоритъм, за намирането на всички стойности на функцията на Ойлер, φ(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.