python - 检查 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 位开始就开始做一些神秘的事情。因此，例如它为“aaaaaaaaaaaaaaa”的编码提供了正确的输出，但没有为“python”提供正确的输出。对于大数字，它似乎执行了太多次 while code % i == 0 循环(“python”的第一个字母为 176，而它应该只是 16)。

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

Answer 1

Python 3 中的

/= 返回 double 浮点值。 (和 math.ceil 一样，顺便说一句。)浮点值没有任意精度。您可以改用 //= 。这总是导致一个整数。 (它给出了结果的底数。)

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