Объяснить проблему с плавающей точкой в ​​факторизации - PullRequest
Новая
       30

Объяснить проблему с плавающей точкой в ​​факторизации

0 голосов
/ 19 января 2011

Мне не хватает здесь технического слова, но проблема здесь в том, чтобы либо изменить int на float, либо float на int. 

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

Ответы [ 3 ]

2 голосов
/ 19 января 2011

Это выражение является вашей непосредственной проблемой: 

float(factorize(n/candidate))

factorize возвращает список, но float требует, чтобы его аргумент был строкой или числом.

(Ваш кодимеет много-много других проблем, но, возможно, вам лучше открыть их для себя ...)

0 голосов
/ 19 января 2011

Не могу понять, что имел в виду Гарет 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) - большое преуменьшение, лол, что я могу найти в Google, давайте рассмотрим плохой результат с большим простым числом. 10003 создает как минимум 10002! подпроцессов, 10003 pawns 10002, поскольку каждый сбой не может быть оценен до тех пор, пока каждый из их подпроцессов не будет оценен и каждый подпроцесс n будет иметь n-1 подпроцессов. Хороший пример, как не факторизовать.

0 голосов
/ 19 января 2011

Обратите внимание, что вы возвращаете 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
...