python - 查找字符 ASCII 值最接近的质数 --- Python

Question

我从用户那里获取一个字符串输入，将其分解为一个字符列表，将每个字符转换为其 ASCII 值，然后搜索最近的素数。将(素数)ASCII 值转换回字符列表，将其连接在一起并将其打印在屏幕上。听起来很简单，但我发现试图找到最接近的素数很棘手。

def is_prime(num):
    if num > 1:
        for n in range(2, num):
            if (num % n) == 0:
                return False
        else:
            return True
    else:
        return False


test_cases = int(input())


for _ in range(test_cases):
    string = str(input())
    array = list(string)
    result_array = []

    for i in array:
        if is_prime(ord(i)):
            result_array.append(i)
        else:
            pass

    print("".join(result_array))

最后一行的“pass”语句只是为了得到一个无错误的代码，直到我找到解决方案。这就是搜索进行的部分。

Answer 1

你的算法无法工作，因为它永远不会解决“最接近素数”的问题(请注意，检查这样的素数效率不高:最大边界可以是n**0.5+1 )

也就是说，这个问题对于小写字母有一个缺陷:

质数从 113 跳到 127。对于高位小写字母，最接近的质数是 127，这是不可打印的。

所以我会坚持使用大写字母(除非我们想打印最接近的最低素数，在这种情况下小写字母就可以了)

我会做的是:

• 生成/复制从 0 到 97 的素数列表(Z 的 ASCII 为 96)
• 对字符进行循环，并使用bisect模块查找字符ASCII码在素数列表中的插入位置(对于bisect，必须对其进行排序 才能正常工作)。
• 然后检查上限是否比下限更接近，并选择素数列表的索引。
• 摆弄插入索引以避免错误(就像我的帖子的第一个版本一样)
• 添加到列表。 最后加入

代码:

import bisect

# list sampled from https://primes.utm.edu/lists/small/1000.txt
# ASCII code for 'A' is 65, no need to go lower
primes = [int(x) for x in """61 67     71     73     79     83     89     97""".split()]

word = "ABCDEFGHIJKLMNOPRSTUVWXYZ"

primeword = []
for w in word:
    ow = ord(w)
    i = bisect.bisect_left(primes,ow)
    delta1 = abs(ow-primes[i])
    delta2 = abs(ow-primes[i-1])
    # select this index or next index (no risk for out of range here)
    primeword.append(chr(primes[i + int(delta2 > delta1) - 1]))

print("".join(primeword))

这给了我:

CCCCCGGGIIIIOOOOSSSSSYYYY

编辑:既然我们生成了素数，我们也可以直接生成字符的查找表并使用str.translate:

primeword_dict = {65: 'C', 66: 'C', 67: 'C', 68: 'C', 69: 'C', 70: 'G', 71: 'G', 72: 'G', 73: 'I', 74: 'I', 75: 'I', 76: 'I', 77: 'O', 78: 'O', 79: 'O', 80: 'O', 82: 'S', 83: 'S', 84: 'S', 85: 'S', 86: 'S', 87: 'Y', 88: 'Y', 89: 'Y', 90: 'Y'}
print(word.translate(primeword_dict))

这会更快更短，并且允许传递像“HELLO WORLD.”这样的字符串(其中包含空格和标点符号)，并且仅更改字母而其他符号保持不变。