检查 python 中（某种）大数的整除性

Question

我一直在 python 中编写一个简单的程序，它使用 Gödel's encoding 将字符串编码为数字。这里有一个快速概述：你取字符串的第一个字母，找到它在字母表中的位置 (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 位开始就开始做一些神秘的事情。因此，例如它为 "aaaaaaaaaaaaaa" 的编码提供了正确的输出，但没有为 "python" 提供正确的输出。对于大数字，它似乎执行了 while code % i == 0 循环太多次（"python" 的第一个字母为 176，而它应该只是 16）。

这只是 python 中 mod 函数的问题吗？听起来很奇怪，因为 20 位数字对于计算机来说并没有那么长。我的代码有错误吗？感谢所有的帮助。我自己不是程序员，但我正在努力学习做这样的事情。因此，欢迎任何建设性的批评。

Answer 1

/= in Python 3 returns 一个 double-precision 浮点值。（和 math.ceil 一样，顺便说一句。）浮点值没有任意精度。您可以改用 //=。这总是导致一个整数。（它给出了结果的下限。）

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

检查 python 中（某种）大数的整除性

Checking divisibility for (sort of) big numbers in python

python

primes

prime-factoring