在python中检查(某种)大数字的可分性

Question

我一直在python中编写一个简单的程序,使用Gödel的编码将字符串编码为数字.这是一个快速概述:你取字符串的第一个字母,找到它在字母表中的位置(a - > 1,b - > 2,...,z - > 26)并将第一个素数(2)提高到这种力量.你取字符串中的第二个字母和第二个素数(3),依此类推.这是代码:

import string, math
alphabet = list(string.ascii_lowercase)

def primes(n):
    "Returns a list of primes up to n."

    primes = [2, 3]
    i = 5
    while i < n:
        l = math.ceil(math.sqrt(i))
        k = math.ceil(math.sqrt(i+2))
        for p in primes[:l]:
            if i % p == 0:
                break
        else:
            primes.append(i)
        for p in primes[:k]:
            if (i+2) % p == 0:
                break
        else:
            primes.append(i+2)
        i += 6
    return primes

def Encode(string):
    "Encodes a string using Godel's encoding."

    enc = 1
    p = primes(100)
    for i in range(len(string)):
        enc = enc*(p[i]**(alphabet.index(string[i])+1))
    return enc

def Decode(code):
    "Decodes a Godel's encoding into a string."

    dec = ""
    for i in primes(100):
        count = 0
        while code % i == 0:
            code /= i
            count += 1
        if count == 0: #If we've found a prime that doesn't divide code, 
                       #there are no more letters to be added.
            break
        else:
            dec += alphabet[count-1]
    return dec

primes()函数适用于我的意图和目的,Encode()也是如此.现在Decode()是有趣的部分.它适用于长达15位数的编码,但从~20位开始做一些神秘的东西.因此,例如,它为"aaaaaaaaaaaaa"编码提供了正确的输出,但没有为"python"编码.对于大数字,它似乎执行while code % i == 0循环次数太多次(对于"python"的第一个字母为176,它应该只有16).

这只是python中mod函数的一个问题吗？听起来很奇怪,因为计算机的20位数字并不长.我的代码中有错误吗？谢谢你的帮助.我自己不是程序员,但我正在努力学习做这样的事情.因此,任何建设性的批评都是受欢迎的.

Answer 1

/=在Python 3中返回一个双精度浮点值。（顺便说一句math.ceil，也是如此。）浮点值不具有任意精度。你可以用//=它来代替。这总是会产生一个整数。（它给出了结果的下限。）

（我之前说过 math.ceil 是你的罪魁祸首。我认为情况并非如此，但尽管如此，你可能不应该使用浮点值来索引列表。如果你需要运行相同的代码在 Python 2 中会失败。您可以使用 将其转换回整数int(math.ceil(...))，尽管您可能需要考虑完全避免浮点计算，因为对于足够大的值，事情将开始崩溃。）