Re: [問題] 關於求質數的問題
※ 引述《v3dys6f3a3j5 (San)》之銘言：
: 這是我們老師給的題目和解答
: 我想問為什麼他求是否為質數是用 if is_prime(n)
: 不是用%整除去算
: 我聽我們老師說這是一個函式
: 問題是我用print執行之後
: 是錯誤
: 我去網站上找質數的求法
: 都是用整除去求的
你的問題應該是對函式運作不熟悉
你們老師的確是用整除去求的... "if n % i == 0" 就是去對每個i(2, 3, 4... n-1)
一個一個去除看看看有沒有整除 有整除就是找到一個因子 那麼n就不是質數
比如n = 35 我要試試看n=35這個數是不是質數 於是使用is_prime(35)進去測
方法就是我去測看看他有沒有可以整除的因子 於是從2開始慢慢往上找...2阿 3阿 4阿
去除35除看看能不能整除 中途如果發現: 阿哈! 我找到了一個數i = 5可以把35整除
於是我後面不用再測啦 直接回傳一個答案"不是"(False) 然後那個迴圈就不再執行
(return等於是跳出迴圈 迴圈以及後面的東西等等都不再執行 包括後面那個return True)
如果最後 一直找不到 找到34 這個迴圈都沒有找到因子 那麼最後只好執行下一個指令:
return True(對 他是質數)
後面那個max_prime是個遞迴函式 大意就是如果:if is_prime(n) 發現n的確是個質數
那麼就不用繼續往下執行啦 廢話不多說 這個函式就return n (也就是回傳n 給print
印出來)
但如果我發現n 不是質數呢? 比如你要找的區間是[10, 100]之間最大的質數 我發現
100不是阿 那麼好吧 我就找看看99是不是(max_prime(10, 99)) 結果我發現他也不是
往下找 直到找到97 符合了base case: if is_prime(97) 於是我把97傳出去給print印
之後的程式就不執行了
如果看的懂上面的 那麼你會發現這支程式可以改的更快(python很慢的)
尤其遞迴要一直定住不動 再發個記憶體給下一個遞迴函式用 很浪費時間
因此如果你可以用以下的邏輯改程式 程式就會變快
1. max_prime遞迴迴圈return max_prime(m, n-1)不要一個一個去算 而是當(n-1)%2==1
時才傳進去:
elif m<n and (n-1)%2==1
原因在於質數除了2以外絕對不是偶數 我不用浪費時間去check看看98 96 94這些數是不是
偶數.
2.既然1.已經剃掉n是偶數的可能性 那麼is_primer的for i 迴圈也不用一個一個去跑
我只需要跑i=奇數的迴圈就好了 i=(3,5,7,9.....)
hint: 偶數的倍數 尾數必然是偶數
3.把is_pime()內的range(2, n) 改成 range(2, sqrt(n) + 1)
這三個改了之後 對於n很大的狀況會有非常巨大的速度差距.
: 高手可以幫我解答一下嗎
: 題目d.寫一完整函式，計算[m,n]之間最大的質數；如果該質數不存在，則傳回-1。
: def is_prime(n):
: for i in range(2,n):
: if n%i==0:
: return False
: return True
: def max_prime(m,n):
: if is_prime(n):
: return n
: elif m<n:
: return max_prime(m,n-1)
: return -1
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.240.163.93
※ 編輯: DreamLoser 來自: 111.240.163.93 (01/13 12:19)
討論串 (同標題文章)