Euler 72Python3项目

Question

其思想是求分母d<；=1000000的不可约分数的个数。这是我使用素筛和Euler的totent函数实现的：

target=10**6
s=0
def primesSieve(limit):
    dictPrimes = {x:True for x in range(2, limit+1)}
    for i in dictPrimes:
        if dictPrimes[i]:
            for f in range(2*i,limit+1, i):
                dictPrimes[f] = False
    return([i for i in dictPrimes if dictPrimes[i]==True])
primes=primesSieve(10**3)
def tot(n,primes):
    result=n
    for i in primes:
        if n%i==0: result-=result/i
    if result==n: result-=1
    return result
for n in range(2,target+1):
    s+=tot(n,primes)
print(s)

我知道这不是最有效的方法，但我想它也应该起作用。然而，我没有得到正确的答案。请帮我找出错误。谢谢！你知道吗

更新 问题是筛子也必须达到1000000。现在我得到了正确的答案。你知道吗