在 Python 中寻找回文素数的优化算法
Optimizing algorithm for finding palindromic primes in Python
我一直在尝试解决一个 LeetCode problem，它接受一个输入数字（小于 10^8）和 returns 下一个回文素数。此外，答案保证存在且小于 2 * 10^8。我的方法似乎适用于大多数数字，但运行时间显着增加，LeetCode 告诉我输入特定数字（如 9989900）时我已经超过了时间限制。是因为回文素数之间的差距在那个范围内很大吗？
这是我写的代码。
import time
start = time.time()
def is_prime(num: int) -> bool:
if num < 2:
return False
elif num == 2 or num == 3:
return True
if num % 6 != 1 and num % 6 != 5:
return False
else:
for i in range(3, int(num ** 0.5) + 1, 2):
if num % i == 0:
return False
else:
return True
def is_palindrome(num: int) -> bool:
return str(num) == str(num)[::-1]
class Solution:
def primePalindrome(self, N: int):
if N == 1:
return 2
elif 8 <= N < 11:
return 11
elif is_prime(N) and is_palindrome(N):
return N
# To skip even numbers, take 2 cases, i.e., when N is even and when N is odd
elif N % 2 == 0:
for i in range(N + 1, 2 * 10 ** 8, 2):
if len(str(i)) % 2 == 0: # Because even length palindromes are divisible by 11
i += 2
elif is_palindrome(i):
if is_prime(i):
return i
else:
continue
else:
for i in range(N, 2 * 10 ** 8, 2):
if len(str(i)) % 2 == 0:
i += 2
elif is_palindrome(i):
if is_prime(i):
return i
else:
continue
obj = Solution()
print(obj.primePalindrome(9989900)) # 100030001
print(time.time() - start) # 9 seconds
我的解决方案是否因为循环和条件语句太多而变慢？如何减少运行时间？最好在不使用任何外部 libraries/packages 的情况下解决这个问题。谢谢。
鉴于顺序检查 primes/palindromes 不够快，我想到了这种“数字组装”方法：
鉴于素数只能以数字1、3、7或9结尾，回文数也只能以这些数字开头。因此，如果我们在第一个和最后一个之间生成回文数字，我们将得到更少的数字来检查“素数”。
例如：1xxxxxx1、3xxxxxx3、7xxxxxx7 和 9xxxxxx9
这些中间部分也必须是回文，所以我们只考虑一半的数字：1xxxxyyy1 其中yyy 是xxx 的镜像。对于奇数大小的中间，我们将有 xxzyy，其中 zyy 是 xxz 的镜像。
结合顺序生成first/last位和中间的数字，我们可以得到N之后的下一个数字。通过顺序生成最高有效位（即xxx部分）我们确定组成的数字将以递增的顺序生成。
def isPrime(n):
return n==2 if n<3 or n%2==0 else all(n%d for d in range(3,int(n**0.5)+2,2))
def nextPalPrime(N):
digits = list(map(int,str(N)))
while True:
if digits[0] not in (1,3,7,9): # advance first/last digits
digits[0] = [1,1,3,3,7,7,7,7,9,9][digits[0]]
digits[1:] = [0]*(len(digits)-1)
digits[-1] = digits[0]
midSize = (len(digits)-1)//2
midStart = int("".join(map(str,digits[1:1+midSize] or [0])))
for middle in range(midStart,10**midSize): # generate middle digits
if midSize:
midDigits = list(map(int,f"{middle:0{midSize}}")) # left half of middle
digits[1:1+midSize] = midDigits # set left half
digits[-midSize-1:-1] = midDigits[::-1] # set mirrored right half
number = int("".join(map(str,digits)))
if number>N and isPrime(number): # check for prime
return number
digits[0] += 1 # next first digit
if digits[0] > 9: digits = [1]+[0]*len(digits) # need more digits
输出：
pp = 1000
for _ in range(20):
pp = nextPalPrime(pp)
print(pp)
10301
10501
10601
11311
11411
12421
12721
12821
13331
13831
13931
14341
14741
15451
15551
16061
16361
16561
16661
17471
性能：
from time import time
start=time()
print(nextPalPrime(9989900),time()-start)
100030001 0.023847103118896484
没有偶数位数
最初我很惊讶这些解决方案从来没有产生偶数位的素数。但是分析回文数的组成我意识到那些总是 11 的倍数（所以不是质数）：
abba = a*1001 + b*110
= a*11*91 + b*11*10
= 11*(a*91 + b*10)
abccba = a*100001 + b*10010 + c*1100
= a*11*9091 + b*11*910 + c*11*100
= 11*(a*9091 + b*910 + c*100)
abcddcba = a*10000001 + b*1000010 + c*100100 + d*110000
= a*11*909091 + b*11*90910 + c*11*9100 + d*11*10000
= 11*(a*909091 + b*90910 + c*9100 + d*10000)
abcdeedcba = a*1000000001 + b*100000010 + c*10000100 + d*10010000 + e*11000000
= a*11*90909091 + b*11*9090910 + c*11*909100 + d*11*910000 + e*11*1000000
= 11*(a*90909091 + b*9090910 + c*909100 + d*910000 + e*1000000)
使用这个观察和更多的数值方法，我们得到了很好的性能提升：
def nextPalPrime(N):
for width in range(len(str(N)),10):
if width%2==0: continue
size = width//2
factors = [(100**(size-n)+1)*10**n for n in range(size)]+[10**size]
for firstDigit in (1,3,7,9):
if (firstDigit+1)*factors[0]<N: continue
for middle in range(10**size):
digits = [firstDigit]+[*map(int,f"{middle:0{size}}")]
number = sum(f*d for f,d in zip(factors,digits))
if number>N and isPrime(number):
return number
from time import time
start=time()
print(nextPalPrime(9989900),time()-start)
100030001 0.004210948944091797
我一直在尝试解决一个 LeetCode problem，它接受一个输入数字（小于 10^8）和 returns 下一个回文素数。此外，答案保证存在且小于 2 * 10^8。我的方法似乎适用于大多数数字，但运行时间显着增加，LeetCode 告诉我输入特定数字（如 9989900）时我已经超过了时间限制。是因为回文素数之间的差距在那个范围内很大吗？ 这是我写的代码。
import time
start = time.time()
def is_prime(num: int) -> bool:
if num < 2:
return False
elif num == 2 or num == 3:
return True
if num % 6 != 1 and num % 6 != 5:
return False
else:
for i in range(3, int(num ** 0.5) + 1, 2):
if num % i == 0:
return False
else:
return True
def is_palindrome(num: int) -> bool:
return str(num) == str(num)[::-1]
class Solution:
def primePalindrome(self, N: int):
if N == 1:
return 2
elif 8 <= N < 11:
return 11
elif is_prime(N) and is_palindrome(N):
return N
# To skip even numbers, take 2 cases, i.e., when N is even and when N is odd
elif N % 2 == 0:
for i in range(N + 1, 2 * 10 ** 8, 2):
if len(str(i)) % 2 == 0: # Because even length palindromes are divisible by 11
i += 2
elif is_palindrome(i):
if is_prime(i):
return i
else:
continue
else:
for i in range(N, 2 * 10 ** 8, 2):
if len(str(i)) % 2 == 0:
i += 2
elif is_palindrome(i):
if is_prime(i):
return i
else:
continue
obj = Solution()
print(obj.primePalindrome(9989900)) # 100030001
print(time.time() - start) # 9 seconds
我的解决方案是否因为循环和条件语句太多而变慢？如何减少运行时间？最好在不使用任何外部 libraries/packages 的情况下解决这个问题。谢谢。
鉴于顺序检查 primes/palindromes 不够快，我想到了这种“数字组装”方法：
鉴于素数只能以数字1、3、7或9结尾，回文数也只能以这些数字开头。因此，如果我们在第一个和最后一个之间生成回文数字，我们将得到更少的数字来检查“素数”。
例如：1xxxxxx1、3xxxxxx3、7xxxxxx7 和 9xxxxxx9
这些中间部分也必须是回文，所以我们只考虑一半的数字：1xxxxyyy1 其中yyy 是xxx 的镜像。对于奇数大小的中间，我们将有 xxzyy，其中 zyy 是 xxz 的镜像。
结合顺序生成first/last位和中间的数字，我们可以得到N之后的下一个数字。通过顺序生成最高有效位（即xxx部分）我们确定组成的数字将以递增的顺序生成。
def isPrime(n):
return n==2 if n<3 or n%2==0 else all(n%d for d in range(3,int(n**0.5)+2,2))
def nextPalPrime(N):
digits = list(map(int,str(N)))
while True:
if digits[0] not in (1,3,7,9): # advance first/last digits
digits[0] = [1,1,3,3,7,7,7,7,9,9][digits[0]]
digits[1:] = [0]*(len(digits)-1)
digits[-1] = digits[0]
midSize = (len(digits)-1)//2
midStart = int("".join(map(str,digits[1:1+midSize] or [0])))
for middle in range(midStart,10**midSize): # generate middle digits
if midSize:
midDigits = list(map(int,f"{middle:0{midSize}}")) # left half of middle
digits[1:1+midSize] = midDigits # set left half
digits[-midSize-1:-1] = midDigits[::-1] # set mirrored right half
number = int("".join(map(str,digits)))
if number>N and isPrime(number): # check for prime
return number
digits[0] += 1 # next first digit
if digits[0] > 9: digits = [1]+[0]*len(digits) # need more digits
输出：
pp = 1000
for _ in range(20):
pp = nextPalPrime(pp)
print(pp)
10301
10501
10601
11311
11411
12421
12721
12821
13331
13831
13931
14341
14741
15451
15551
16061
16361
16561
16661
17471
性能：
from time import time
start=time()
print(nextPalPrime(9989900),time()-start)
100030001 0.023847103118896484
没有偶数位数
最初我很惊讶这些解决方案从来没有产生偶数位的素数。但是分析回文数的组成我意识到那些总是 11 的倍数（所以不是质数）：
abba = a*1001 + b*110
= a*11*91 + b*11*10
= 11*(a*91 + b*10)
abccba = a*100001 + b*10010 + c*1100
= a*11*9091 + b*11*910 + c*11*100
= 11*(a*9091 + b*910 + c*100)
abcddcba = a*10000001 + b*1000010 + c*100100 + d*110000
= a*11*909091 + b*11*90910 + c*11*9100 + d*11*10000
= 11*(a*909091 + b*90910 + c*9100 + d*10000)
abcdeedcba = a*1000000001 + b*100000010 + c*10000100 + d*10010000 + e*11000000
= a*11*90909091 + b*11*9090910 + c*11*909100 + d*11*910000 + e*11*1000000
= 11*(a*90909091 + b*9090910 + c*909100 + d*910000 + e*1000000)
使用这个观察和更多的数值方法，我们得到了很好的性能提升：
def nextPalPrime(N):
for width in range(len(str(N)),10):
if width%2==0: continue
size = width//2
factors = [(100**(size-n)+1)*10**n for n in range(size)]+[10**size]
for firstDigit in (1,3,7,9):
if (firstDigit+1)*factors[0]<N: continue
for middle in range(10**size):
digits = [firstDigit]+[*map(int,f"{middle:0{size}}")]
number = sum(f*d for f,d in zip(factors,digits))
if number>N and isPrime(number):
return number
from time import time
start=time()
print(nextPalPrime(9989900),time()-start)
100030001 0.004210948944091797