0

我正在尝试将一些 C++ 转换为 Python。

C++ 可以在以下位置找到

https://gist.github.com/1635288

from prime import prime
from fractions import gcd
from copy import copy
def phi(n, primes):
    if n < 2:
        return 0

    if n in primes:
        return n - 1

    if (n & 1) == 0:
        m = n >> 1
        #return ~(m & 1) ? phi(m, primes) << 1 : phi(m, primes)
        if ~(m & 1):
            return phi(m, primes) << 1
        else:
            return phi(m, primes)

    for i in primes:
        if i > n:
            break

        if n % i:
            continue

        m = copy(i)
        o = n / m
        d = gcd(m, o)
        #return d == 1 ? phi(m) * phi(o) : phi(m) * phi(o) * d / phi(d)
        if d == 1:
            return phi(m, primes) * phi(o, primes)
        else:
            return phi(m, primes) * phi(o, primes) * d / phi(d, primes)

primes = []
for i in range(3, 10000000, 2):
    if prime(i):
        primes.append(i)

for i in range(80, 90): # a test to see if I am getting correct results
    print phi(i, primes)
    # returns   64, 54, 80, 82, 48, 64, 84, 56, 80, 88
    # should be 32, 54, 40, 82, 24, 64, 42, 56, 40, 88

基本上，该函数为奇数 n 返回正确的 phi 值，但为偶数 n 返回正确值的两倍。我怀疑我出错的地方是

m = copy(i)

而 C++ 是

int m = *p;

我查阅了维基百科，发现这将 m 定义为 p指向的值。这是问题吗？如果不是，那是什么？

4

2 回答 2

3

我认为您应该使用if not (m & 1), 而不是if ~(m & 1)，因为前者是检查奇数/偶数，而后者只有false在您将 -1 传递给它时才会返回。

波浪号 ( ~) 是按位否定运算符。对于整数值，它认为~x == -x-1，在您的情况下根本不会发生。

于 2012-08-20T12:11:52.003 回答
0

int m = *p实际上调用operator*of p，它是一个迭代器。它将返回迭代器当前所在的整数。对于给定的 C++ 代码，这只是语法糖化（稍微提高了一点性能），以避免*p*每次都编写。

于 2012-08-20T12:10:06.020 回答