py66求优化

P1217 [USACO1.5] 回文质数 Prime Palindromes

mohammed24 @ 2024-10-31 20:35:38

def pri(i): if i<2: return False else: x=int(i**0.5) for j in range(2,x+1): if i%j==0: return False break a,b=map(int,input().split()) for i in range(a,b): I=str(i) if I==I[::-1] and pri(i)!=False: print(i)

by luoguguler @ 2024-11-07 09:55:59

我也是python， 也是66，不过可能有两个优化点

  1. 试试手动跳过所有位数为偶数的数字（比如除了11之外的两位数，所有四位数、六位数和八位数）。位数为偶数的数字性质特殊，使得它们必不是回文质数。比如说四位数，假设一个四位数是回文质数，那么它一定形如：1000A+100B+10B+1A（A和B为未知数），即1001A+110B。1001A可被11整除得91A，110B同理。这个性质适用于所有位数为偶数的数字，跳过之后能省不少时间。
  2. 质数有一个性质：除了2和3之外，所有质数都为6x-1或6x+1（比方说5,7；11,13；17,19...）。可以简化质数判断

当然还是第一个思路效果最好，当时在自己的机器上测试基本是从1.2s优化到了0.8秒，可惜还是超时。结果后来重构的时候出了点问题，无奈之后再磕。毕竟如果用的是随便一个python之外的语言肯定已经跑通了

|