创建一个函数，该函数使用Python计算使用给定分母可以生成多少适当的分数

Question

目标：构建一个函数，用于计算使用给定分母可以构建多少个适当分数

问题：Codewars是一个用于提交代码的平台。提交后，它将不接受我的代码，因为即使我通过了所有测试用例，它也没有效率。有人可以建议我如何进一步优化我的代码吗

代码：

from fractions import Fraction 

def proper_fractions(n):
    
    count = 0
    
    for i in range(1,n):
        fractionA = Fraction(i, n) 
        if fractionA.denominator == n:
            count+=1
    
    return count

样本测试：

Test.assert_equals(proper_fractions(1),0)
Test.assert_equals(proper_fractions(2),1)
Test.assert_equals(proper_fractions(5),4)
Test.assert_equals(proper_fractions(15),8)
Test.assert_equals(proper_fractions(25),20)

Answer 1

这应该快7到8倍：

from math import gcd

def fracCount(N): return sum(gcd(d,N)==1 for d in range(1,N))

对于给定的N，将有N-1个分数的最大值：1/N，2/N，3/N。。。（N-1）/N。当分子和分母可以被一个公共除法器（我们可以用gcd检测到）除时，不属于适当分数的分数

输出：

print(fracCount(1))  # 0
print(fracCount(2))  # 1
print(fracCount(5))  # 4
print(fracCount(15)) # 8
print(fracCount(25)) # 20

[编辑]

对于更快的解决方案，您可以通过查找N的素数因子的所有倍数来获得“不正确”的分子。您需要一个返回如下素数因子的函数。从N-1中减去这些不正确分子的数目，得到正确分数的计数

def primeDivs(N):
    p = 2
    while N>=p*p:
        if N%p == 0:   yield p
        while N%p==0:  N //= p
        p += 1 + (p&1)
    if N>1 : yield N

def fracCount(N):
    return N-1-len({f for p in primeDivs(N) for f in range(p,N,p)})

这个分数比适当的分数快大约100倍

[EDIT2]使用Euler的toticent函数更快（在N的大值上）：

def totient(N):
    tot  = N
    for p in primeDivs(N):
        tot -= tot//p
    return tot

def properFractions(N): return 0 if N<2 else totient(N)

对于N=10000，它比适当的_分数快3000倍以上