Kiểm tra số chia cho (loại) số lớn trong python

Question

Tôi đã viết một chương trình đơn giản trong python mã hóa chuỗi thành một số bằng cách sử dụng Gödel's encoding. Dưới đây là tổng quan nhanh: bạn lấy chữ cái đầu tiên của chuỗi, tìm vị trí của nó trong bảng chữ cái (a -> 1, b -> 2, ..., z -> 26) và tăng số nguyên tố đầu tiên (2) lên sức mạnh này. Bạn lấy chữ thứ hai trong chuỗi và số nguyên tố thứ hai (3) và vân vân. Đây là mã:

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 

Hàm nguyên tố() hoạt động cho mục đích và mục đích của tôi và do đó, mã hóa(). Bây giờ Decode() là phần thú vị. Nó hoạt động cho mã hóa lên đến ~ 15 chữ số dài nhưng bắt đầu làm một số công cụ thần bí bắt đầu từ ~ 20 chữ số. Vì vậy, ví dụ nó cung cấp cho đầu ra đúng cho các mã hóa của "aaaaaaaaaaaaaa" nhưng không cho "python". Đối với những con số lớn, nó dường như thực hiện vòng lặp while code % i == 0 quá nhiều lần (176 cho chữ cái đầu tiên của "python" khi nó chỉ là 16).

Đây có phải là vấn đề với hàm mod trong python không? Âm thanh lạ như 20 chữ số không phải là tất cả những gì dài cho một máy tính. Có lỗi trong mã của tôi không? Cảm ơn vì sự giúp đỡ. Tôi không phải là một lập trình viên nhưng tôi đang cố gắng học những thứ như thế này. Do đó bất kỳ lời chỉ trích mang tính xây dựng nào đều được chào đón.

Answer 1

/= bằng Python 3 trả về giá trị dấu phẩy động kép chính xác kép. (Cũng như math.ceil, btw.) Giá trị điểm nổi không có độ chính xác tùy ý. Thay vào đó, bạn có thể sử dụng //=. Điều đó luôn dẫn đến một số nguyên. (Nó cung cấp cho sàn của kết quả.)

(trước đây tôi đã nói rằng math.ceil là thủ phạm chính của bạn. Tôi không nghĩ vậy, nhưng dù sao, bạn có lẽ không nên sử dụng một giá trị dấu phẩy động Nếu bạn cần chạy cùng một mã trong Python 2 sẽ thất bại, bạn có thể đưa nó trở lại một số nguyên bằng cách sử dụng int(math.ceil(...)), mặc dù bạn có thể cân nhắc tránh các tính toán dấu phẩy động, vì mọi thứ sẽ bắt đầu chia nhỏ cho các giá trị đủ lớn.)