计算欧拉函数

Question

背景

欧拉函数托蒂亚 φ(n)定义为相对于n素数的小于或等于n的整数，即x在0 < x <= n中的可能值的个数( gcd(n, x) == 1 )。我们以前有过一个 一些 托蒂亚-相关 挑战，但从来没有计算过。

totient函数到整数的映射是OEIS A000010。

挑战

给定整数n > 0，计算φ(n)。您可以通过命令行参数、标准输入、函数参数或任何其他合理的方法获取输入。您可以通过标准输出、返回值或任何其他合理的方法提供输出。匿名函数是可以接受的。您可能假设输入不会溢出您存储整数的自然方法，例如C中的int，但您必须支持最多255个输入。如果您的语言有内置的函数，您可以不使用它。

示例

φ(1) => 1
φ(2) => 1
φ(3) => 2
φ(8) => 4
φ(9) => 6
φ(26) => 12
φ(44) => 20
φ(105) => 48

最短答案(以字节为单位)获胜。如果您的语言使用的编码不是UTF-8，请在您的回答中提及它。

Answer 1

矩阵，7字节

t:Zd1=s

你可以TryItOnline。最简单的想法，使向量1到N，并取每个元素的gcd与N (Zd做gcd)。然后，找出哪些元素等于1，然后用向量和得到答案。

Answer 2

Python2，44个字节

f=lambda n,d=1:d/n or-f(d)*(n%d<1)-~f(n,d+1)

较少的高尔夫球：

f=lambda n:n-sum(f(d)for d in range(1,n)if n%d<1)

使用n的除数的欧拉函数之和为n的公式：

然后，ϕ(n)的值可以递归地计算为n减去非平凡除数上的和。实际上，这是对身份函数执行M bius反演。我在计算M bius函数的高尔夫球中使用了同样的方法。

感谢丹尼斯用更好的大小写保存了1个字节，将+n的初始值扩展到+1中，用于每个n循环，作为-~完成。

Answer 3

果冻，4字节

Rgċ1

在网上试试！

解释

Rgċ1   Main monadic chain. Argument: z

R      Yield [1 2 3 .. z].
 g     gcd (of each) (with z).
  ċ1   Count the number of occurrences of 1.

内置

ÆṪ

在网上试试！

解释

ÆṪ   Main monadic chain. Argument: z

ÆṪ   Totient of z.