2020-12-14 00:33:55 +05:30
|
|
|
/*
|
|
|
|
|
author sandyboypraper
|
|
|
|
|
|
|
|
|
|
Here is the EulerTotientFunction.
|
|
|
|
|
it is also represented by phi
|
|
|
|
|
|
|
|
|
|
so EulersTotientFunction(n) (or phi(n)) is the count of numbers in {1,2,3,....,n} that are relatively
|
|
|
|
|
prime to n, i.e., the numbers whose GCD (Greatest Common Divisor) with n is 1.
|
|
|
|
|
*/
|
|
|
|
|
|
2020-12-14 12:26:08 +05:30
|
|
|
const gcdOfTwoNumbers = (x, y) => {
|
|
|
|
|
// x is smaller than y
|
|
|
|
|
// let gcd of x and y is gcdXY
|
2021-02-05 17:59:38 +05:30
|
|
|
// so it divides x and y completely
|
|
|
|
|
// so gcdXY should also divide y%x (y = gcdXY*a and x = gcdXY*b and y%x = y - x*k so y%x = gcdXY(a - b*k))
|
2025-09-04 07:02:03 +03:00
|
|
|
// and gcd(x,y) is equal to gcd(y%x, x)
|
2020-12-14 12:26:08 +05:30
|
|
|
return x === 0 ? y : gcdOfTwoNumbers(y % x, x)
|
2020-12-14 00:33:55 +05:30
|
|
|
}
|
|
|
|
|
|
2020-12-14 12:26:08 +05:30
|
|
|
const eulersTotientFunction = (n) => {
|
|
|
|
|
let countOfRelativelyPrimeNumbers = 1
|
2020-12-14 12:38:08 +05:30
|
|
|
for (let iterator = 2; iterator <= n; iterator++) {
|
|
|
|
|
if (gcdOfTwoNumbers(iterator, n) === 1) countOfRelativelyPrimeNumbers++
|
2020-12-14 12:26:08 +05:30
|
|
|
}
|
|
|
|
|
return countOfRelativelyPrimeNumbers
|
2020-12-14 00:33:55 +05:30
|
|
|
}
|
|
|
|
|
|
2020-12-14 12:26:08 +05:30
|
|
|
export { eulersTotientFunction }
|
