我试图找到一种有效的方法来计算Euler's totient function。
这个密码有什么问题吗?好像不起作用.
def isPrime(a):
return not ( a < 2 or any(a % i == 0 for i in range(2, int(a ** 0.5) + 1)))
def phi(n):
y = 1
for i in range(2,n+1):
if isPrime(i) is True and n % i == 0 is True:
y = y * (1 - 1/i)
else:
continue
return int(y)
9条答案
按热度按时间1l5u6lss1#
根据维基百科上的描述,这里有一个更快的工作方式:
因此,如果n是正整数,则φ(n)是整数k在1 ≤ k ≤ n范围内的个数,且gcd(n,k)= 1。
我不是说这是最快或最干净的,但它的工作。
wsewodh22#
你有三个不同的问题...
y
需要等于初始值n
,而不是1
1.正如一些人在评论中提到的,不要使用整数除法
n % i == 0 is True
没有做你想做的事情,因为Python链接了比较!即使n % i
等于0
,那么0 == 0
也是True
但是0 is True
是False
!使用括号或者直接摆脱与True
的比较,因为这是不必要的。解决这些问题,
fv2wmkja3#
计算范围内每一对的gcd效率不高,也不成比例,你不需要迭代整个范围,如果n不是素数,你可以检查直到其平方根的素数因子,参见https://stackoverflow.com/a/5811176/3393095,然后我们必须通过phi = phi*(1 - 1/prime)更新每个素数的phi。
hs1rzwqc4#
我正在用python开发一个加密库,这就是我正在使用的,
gcd()
是欧几里得计算最大公约数的方法,phi()
是totient函数。yi0zb3m45#
其他用户提到的大多数实现都依赖于调用gcd()或isPrime()函数。如果你要多次使用phi()函数,那么在手工之前计算这些值是值得的。一种方法是使用所谓的sieve算法。
https://stackoverflow.com/a/18997575/7217653 stackoverflow上的这个答案为我们提供了一个快速查找给定数以下所有素数的方法。
好了,现在我们可以在数组中用search替换isPrime()。
现在实际的phi函数:
维基百科给了我们一个明显的例子:www.example.comhttps://en.wikipedia.org/wiki/Euler%27s_totient_function#Example
φ(36)= φ(2^2 * 3^2)= 36 (1 - 1/2)(1 - 1/3)= 30 * 1/2 * 2/3 = 12
换句话说,这表示36的相异素因子是2和3;从1到36的36个整数的一半可被2整除,剩下18个;其中三分之一可以被3整除,剩下12个数与36互质。实际上,还有12个正整数与36互质且小于36:第1、5、7、11、13、17、19、23、25、29、31和35条。
靶病变; DR
换句话说:我们必须找到所有的素因子,然后用foreach prime_factor将这些素因子相乘:n *= 1 - 1/素因子。
ltskdhd16#
看起来你在尝试使用欧拉的乘积公式,但你不是在计算除a的素数的个数,你是在计算与a互质的元素的个数。
此外,由于1和i都是整数,所以除法也是如此,在这种情况下你总是得到0。
rm5edbpk7#
关于效率,我没有注意到任何人提到gcd(k,n)=gcd(n-k,n),利用这个事实可以保存大约一半的工作量,只需从2开始计数(因为1/n和(n-1)/k总是不可约的),每次gcd为1时加2。
k3fezbri8#
下面是orlp答案的一个简短实现。
正如其他人已经提到的,它为性能优化留下了空间。
pzfprimi9#
实际上要计算phi(任意数,比如n)
我们使用Formula
其中p是n的素因子。
因此,您的代码中几乎没有错误:
y
应等于n
2.对于
1/i
,实际上1
和i
都是整数,因此它们的求值也将是整数,因此将导致错误的结果。下面是需要更正的代码。