回文数可被任何给定数字整除

Question

我有以下问题要解决：数字545,5995和15151是可被109整除的三个最小的回文。有九个小于100000的回文可被109整除。

少于10 ** 32的几个回文可以被10000019整除？

所以我的代码如下所示。从理论上讲，我的代码可以正常运行，但要从0到10 **一直计算，这将使我的计算机确实需要几年。

反正有没有改进这个代码？

Python代码：

listPalindroms=[]
for i in range (0,10**32):
    strI = str(i)
    printTrue = 1
    if len(strI) == 1:
        listPalindroms.append(i)
    else:
        if len(strI)%2 ==0:
            FinalVal = int(len(strI)/2)
            for count in range (0,FinalVal):
                if strI[count]!=strI[-count-1]:
                    printTrue = 0
            if printTrue==1: listPalindroms.append(i)
        else:
            FinalVal = int(round(len(strI)/2))-1
            for count in range (0,FinalVal):
                if strI[count]!=strI[-count-1]:
                    printTrue = 0
            if printTrue ==1: listPalindroms.append(i)

i=0
for item in listPalindroms:
    if item%10000019 ==0:
        i = i + 1
print (i)

问题出现在Project Euler 655

Answer 1

你得到0和10**32之间的所有回文，然后使用可分性过滤。但你也可以反过来做。只需找到小于10000019的10**32的倍数，然后检查每个倍数是否为回文。

这样您就可以避免检查回文中不需要的数字。

i = 1
number = 10000019
list_palindromes = []
element = number * i
while element < (10**32):
    e = str(element)
    for j in range(len(e)):
        if e[j] != e[len(e)-j-1]:
            break
        if len(e)-1 == j:
            list_palindromes.append(e)
            print(e)
    i += 1
    element = number * i

Answer 2

好吧，你只需要检查你的除数可以整除的数字，那么为什么在此之前检查数字，并且在递增时，为什么不增加除数呢？

def is_palin(num):
    num_str = str(num)
    for index in range(len(num_str)/2):
        if num_str[index]==num_str[len(num_str)-1-index]:
            continue
        return False
    return True

def multiple(divisor, end):
    count=0
    index = divisor*2
    while index<end:
        if is_palin(index):
            count+=1
        index+=divisor

    return count

if __name__=="__main__":
    print(multiple(109, 100000))
    # print(multiple(10000019, 10**32))

这种方法仍然需要很长时间，我建议找一个更好的方法。