解释因式分解中的浮点-整数问题

Question

我这里缺少一个专业术语，但问题在于要么把整数（int）转换成浮点数（float），要么把浮点数转换成整数。

def factorize(n):
    def isPrime(n):
        return not [x for x in range(2,int(math.sqrt(n)))
                    if n%x == 0]
    primes = []
    candidates = range(2,n+1)
    candidate = 2
    while not primes and candidate in candidates:
        if n%candidate == 0 and isPrime(candidate):

            # WHY ERROR?
            #I have tried here to add float(), int() but cannot understand why it returns err
            primes = primes + [float(candidate)] + float(factorize(n/candidate))
        candidate += 1
    return primes

错误信息 -- 我尝试用一些函数，比如 int() 和 float() 来修复这个问题，但问题依然存在：

TypeError: 'float' object cannot be interpreted as an integer

Answer 1

我不太明白Gareth说的 many, many other problems 是什么意思，问题在于数据清理！

def factorize(n):
    # now I won`t get floats
    n=int(n)

    def isPrime(n):
        return not [x for x in range(2,int(math.sqrt(n)))
                    if n%x == 0]

    primes = []
    candidates = range(2,n+1)
    candidate = 2
    while not primes and candidate in candidates:
        if n%candidate == 0 and isPrime(candidate):
            primes = primes + [candidate] + factorize(n/candidate)
        candidate += 1
    return primes


clearString = sys.argv[1]
obfuscated = 34532.334
factorized = factorize(obfuscated)

print("#OUTPUT "+factorized)


#OUTPUT [2, 2, 89, 97]

更好，但能不能更简单或者少写几行呢？

def factorize(n):
    """ returns factors to n """

    while(1):
            if n == 1:
                    break

            c = 2 

            while n % c != 0:
                    c +=1

            yield c
            n /= c

 print([x for x in factorize(10003)])

时间比较

$ time python3.1 sieve.py 
[100003]

real    0m0.086s
user    0m0.080s
sys 0m0.008s
$ time python3.1 bad.py 
^CTraceback (most recent call last):
  File "obfuscate128.py", line 25, in <module>
    print(factorize(1000003))
  File "obfuscate128.py", line 19, in factorize
    if n%candidate == 0 and isPrime(candidate):
KeyboardInterrupt

real    8m24.323s
user    8m24.320s
sys 0m0.016s

说 at least O(n) 这句话有点保守，哈哈，我从谷歌上找到的信息来看，考虑到大质数的糟糕结果。比如说 10003 个棋子至少需要 10002! 个子进程，10003 个棋子 10002 是因为每个都失败了，必须等到它们每个子进程都评估完才能进行评估，而且每个 n 的子进程会有 n-1 个子进程。这是一个很好的例子，说明了如何不进行因式分解。

Answer 2

注意到你返回的是一个 list（列表），而在这一行：

primes = primes + [float(candidate)] + float(factorize(n/candidate))

但是 float 只能用于数字或字符串，而不能用于列表。

正确的解决方法应该是：

primes = primes + [float(candidate)] + [float(x) for x in factorize(n/candidate)]
# Converting every element to a float

Answer 3

这个表达式就是你现在面临的问题：

float(factorize(n/candidate))

factorize这个函数返回的是一个列表，但float函数需要的参数必须是字符串或者数字。

（你的代码还有很多其他问题，不过也许你自己发现这些问题会更好……）