快捷導(dǎo)航

解決Python中回文數(shù)和質(zhì)數(shù)的問題

更新時間：2019年11月24日 10:08:42 作者：Jock2018

今天小編就為大家分享一篇解決Python中回文數(shù)和質(zhì)數(shù)的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧

一、前言

今天學(xué)習(xí)視頻時課后作業(yè)是找出1000以內(nèi)既是素數(shù)又是回文數(shù)的數(shù)，寫代碼這個很容易，結(jié)果一運行遇到了bug，輸出結(jié)果跟預(yù)期不一樣，調(diào)試了快30min，再接著一通搜索和回看視頻才發(fā)現(xiàn)問題所在。所以特地寫下來，方便以后查看。問題的關(guān)鍵是判斷素數(shù)過程中for…else的用法上（具體看后面代碼）

二、實現(xiàn)判斷素數(shù)的功能

質(zhì)數(shù)（Prime number），又稱素數(shù)，指在大于1的自然數(shù)中，除了1和該數(shù)自身外，無法被其他自然數(shù)整除的數(shù)（也可定義為只有1與該數(shù)本身兩個因數(shù)的數(shù)）。via——Wikipedia

所以采用窮舉法只要在2~n-1的區(qū)間，沒有一個數(shù)能整除n，那么n就是素數(shù)。

對2-n-1區(qū)間進行合理優(yōu)化，假設(shè)x*y=n(x<=y)，那么當x和y相等時，x有最大值。即x=y=sqrt(n)，所以x的區(qū)間就可以限制為2~sqrt(n)+1。還有疑問，可以在再多想想，紙上算一算。

因為這里要用到sqrt()方法，所以需要導(dǎo)入math模塊。

不多說，直接上代碼：

# 求解1000以內(nèi)的所有素數(shù),正確版本
import math

num = 2
count = 0
list_s = []
max_d = 1000
while num < max_d:
 length = int(math.sqrt(num)+1) # 對遍歷范圍進行合理優(yōu)化
 for i in range(2,length): # 注意從2開始
  if num % i == 0:
   break
 else: # 這里的else跟for對齊,而不是跟if,表示只有for順利執(zhí)行時,else才執(zhí)行
  count += 1
  list_s.append(num) # 存入列表
 num += 1
if count == 0:
 print(max_d,'以內(nèi)沒有素數(shù)')
else:
 print(max_d,'以內(nèi)的素數(shù)有',count,'個，分別是：',list_s)

輸出結(jié)果：

這個代碼完全沒有問題，然后下面給出一個有問題的代碼：

# 求解40以內(nèi)的所有素數(shù),錯誤版本
import math

num = 2
count = 0
list_s = []
max_d = 40
while num < max_d:
 length = int(math.sqrt(num)+1) # 對遍歷范圍進行合理優(yōu)化
 for i in range(2,length): # 注意從2開始
  if num % i == 0:
   break
  else: # 這里的else跟if對齊,會導(dǎo)致一個素數(shù)會被寫入int(math.sqrt(num))-1次，同時一些非素數(shù)也會被當做素數(shù)
   count += 1
   list_s.append(num) # 存入列表
 num += 1
if count == 0:
 print(max_d,'以內(nèi)沒有素數(shù)')
else:
 print(max_d,'以內(nèi)的素數(shù)有',count,'個，分別是：',list_s)

輸出結(jié)果：

所以，一定要認真對待循環(huán)中else對齊問題。這個在解決素數(shù)問題中很重要。小結(jié)一下while…else和for…else

只有循環(huán)完所有次數(shù)，才會執(zhí)行 else ，循環(huán)體中有continue存在，也不影響else執(zhí)行。

一旦循環(huán)體中觸發(fā)了break ，就會阻止 else 語句塊的執(zhí)行。

三、實現(xiàn)判斷回文數(shù)的功能

回文數(shù)即從左到右和從右到左一樣。如：12321。

方法：

把已知的num1數(shù)反過來，得到num2，如123變?yōu)?21，采用//10 %10 *10等運算操作，其中還要借助一個臨時變量tmp

判斷如果num1 == num 2，則num1是回文數(shù)，反之不是

代碼如下：

# 求解1000以內(nèi)的所有回文數(shù)
num = 0 # 這里num從0開始
list_h = []
max_d = 10000
count = 0 

while num < max_d:
 tmp = num
 num_p = 0
 while tmp != 0:
  num_p = num_p*10 + tmp % 10
  tmp //= 10
 if num_p == num:
  list_h.append(num)
  count += 1
 num += 1
  
if count == 0:
 print(max_d,'以內(nèi)沒有回文數(shù)')
else:
 print(max_d,'以內(nèi)的回文數(shù)有',count,'個，分別是：',list_h)

更新：對于判斷回文數(shù)或者回文字符串，采用雙端隊列的數(shù)據(jù)結(jié)構(gòu)，會非常簡單。實現(xiàn)如下：

from collections import deque

def palindrome(word):
 dq = deque(word)
 while len(dq) > 1:
  if dq.pop() != dq.popleft():
   return False
 return True

if __name__ == '__main__':
 max_num = 10000
 for i in range(max_num):
  s = str(i)
  if palindrome(s):
   print(i, end=',')

四、實現(xiàn)同時判斷回文數(shù)和質(zhì)數(shù)

需要選擇是否嵌套以及先判斷回文還是先判斷素數(shù)，所以又四個版本。大家可以自己思考每個版本的性能上有無區(qū)別，占用空間有無區(qū)別。因為我也沒有太想明白，所以沒有放上來。

我寫了四個版本，都能實現(xiàn)需求。不過從性能上，在我測試的100-1000000區(qū)間，采用嵌套的先求解回文再判斷素數(shù)要快一些。

不多說，四個版本的代碼全部在寫下面，可以自行刪掉相應(yīng)的'''標記進行測試。

'''
# 版本一、求1000以內(nèi)的回文素數(shù),多層嵌套,先求素數(shù)后回文數(shù)

import math

num = 2
count = 0
list_s = []
list_sh = []
max_d = 1000
while num < max_d:
 length = int(math.sqrt(num)+1)
 for i in range(2,length):
  if num % i == 0:
   break
 else:
  list_s.append(num)
  tmp = num
  num_p = 0
  while tmp != 0:
   num_p = num_p * 10 + tmp % 10
   tmp //= 10
  if num == num_p:
   list_sh.append(num)
   count +=1
 num += 1
print(max_d,'以內(nèi)的素數(shù)有：',list_s)
if count == 0:
 print(max_d,'以內(nèi)沒有既是素數(shù)又是回文數(shù)的數(shù)')
else:
 print(max_d,'以內(nèi)既是素數(shù)又是回文數(shù)的數(shù)有',count,'個，分別是：',list_sh)

'''


'''
# 版本二、求1000以內(nèi)的回文素數(shù),多層嵌套,先求回文數(shù)后求素數(shù)

import math

num = 2
count = 0
list_h = []
list_hs = []
max_d = 1000
while num < max_d:
 tmp = num
 num_p = 0
 while tmp != 0:
  num_p = num_p * 10 + tmp % 10
  tmp //= 10
 if num == num_p:
  list_h.append(num)
  length = int(math.sqrt(num)+1)
  for i in range(2,length):
   if num % i == 0:
    break
  else:
   list_hs.append(num)
   count +=1
 num += 1
print(max_d,'以內(nèi)的素數(shù)有：',list_h)
if count == 0:
 print(max_d,'以內(nèi)沒有既是素數(shù)又是回文數(shù)的數(shù)')
else:
 print(max_d,'以內(nèi)既是素數(shù)又是回文數(shù)的數(shù)有',count,'個，分別是：',list_hs)
'''


'''
# 版本三、求1000以內(nèi)的回文素數(shù)，先求素數(shù)再求回文數(shù)

import math

num = 2
list_s = []
max_d = 1000

while num < max_d:
 length = int(math.sqrt(num)+1)
 for i in range(2,length):
  if num % i == 0:
   break
 else: # 注意這里的else是和for對齊
  list_s.append(num)
 num += 1


count = 0
list_sh = []
for i in list_s:
 tmp = i
 num_p = 0
 while tmp != 0:
  num_p = num_p*10 + tmp % 10
  tmp //= 10
 if num_p == i:
  list_sh.append(i)
  count += 1
  

print(max_d,'以內(nèi)的素數(shù)有：',list_s)
if count == 0:
 print(max_d,'以內(nèi)沒有既是素數(shù)又是回文數(shù)的數(shù)')
else:
 print(max_d,'以內(nèi)既是素數(shù)又是回文數(shù)的數(shù)有',count,'個，分別是：',list_sh)
'''


'''
# 版本四、求1000以內(nèi)的回文素數(shù),先求回文數(shù)，再求素數(shù)

import math

num = 2
list_h = []
max_d = 10000

while num < max_d:
 tmp = num
 num_p = 0
 while tmp != 0:
  num_p = num_p*10 + tmp % 10
  tmp //= 10
 if num_p == num:
  list_h.append(num)
 num += 1


count = 0
list_sh = []
for hn in list_h:
 length = int(math.sqrt(hn)+1)
 for i in range(2,length):
  if hn % i == 0:
   break
 else: # 注意這里的else是和for對齊
  list_sh.append(hn)
  count += 1
  

print(max_d,'以內(nèi)的回文數(shù)有：',list_h)
if count == 0:
 print(max_d,'以內(nèi)沒有既是素數(shù)又是回文數(shù)的數(shù)')
else:
 print(max_d,'以內(nèi)既是素數(shù)又是回文數(shù)的數(shù)有',count,'個，分別是：',list_sh)
'''

五、總結(jié)

這個過程幫助自己更加深刻的理解了if…elif…else 、for…else和while…else以后使用時會更加注意。

以上這篇解決Python中回文數(shù)和質(zhì)數(shù)的問題就是小編分享給大家的全部內(nèi)容了，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: