※ 引述《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)