我的程式碼
for i in range(20000000):
c=0
for j in range(int((20000000-1-i)**0.5)-1):
c+=1
if (20000000-1-i)%c==0:
continue
if (20000000-1-i)%c!=0:
if c==int((20000000-1-i)**0.5)-1:
print(20000000-1-i)
break
我嘗試自己寫了一下，但是我感覺我自己寫出來的程式1.無效率2.有錯誤(但我找不出錯在哪裡)
請問大神能幫我除錯嗎?
已邀請的邦友 {{ invite_list.length }}/5
用range(20000000,1,-1)一行就好了，這是我第一個想到的方法
測2~平方根之間整除
import math
def isPrime(test):
r = 0
#從2開始到測試數的平方根整數間，可以整除的超過1個就不是質數
for t in range(2, int(math.sqrt(test))+1 ):
r += 1 if test % t == 0 else 0
if r>0 :
break #超過0個就不用再拚命測試下去
return r == 0
for i in range(20000000,1,-1):
if isPrime(i):
print(i)
break
平均一個數字只要跑４個for 就結束，負載高的就取平方根的函數
不想要有取平方根的負載的話，你可以把math.sqrt直接換成被測試的數（２～Ｎ），但，這比取平方根來測還大量工作，２０００萬的平方根是４千多，從４千多到２０００萬之間那堆數字，沒意義啊
啊，對了，我忘了說，這個2到平方根的測試方法並未得到完全實證是否為完全可用 (測試到無限大的正整數，沒那麼好的電腦，但在有限資源的環境下測是OK的，還沒找到例外數，我的數學能力只有到小五的程度.. )，如果證實成了可用且高效的算法，記得掛上我的名字就好，但..應該不可能花生
....
只測試到 的話
一些數字會判斷錯誤喔
例如下列這個會回傳 True
print(isPrime(13*13))
AKS是我在網上找到的一個可能的測試方法，至於是不是可信，也只能交給大家去測試看看了..
13×13=169
2 到 log2(169) → 2 ~ 7 ....... 呃，叭噗~
還是2到平方根的算法比較實在
判斷 x 是否為質數，只要確認 x 都不能被「小於等於根號 x 的質數」整除即可
也就是說要判斷二千萬內的質數，可以先找出 以內的所有質數
把它們儲存在一個列表中，後續判斷只要從這些質數來找
下列這個程式是會自動建立質數表，能盡可能減少重複的判斷
import math
# 判斷 x 是否為質數，優先從質數表(primes)中找尋
# 若質數表不足以判斷 x 是否為質數，會自動擴充
def isPrime(x, primes):
n = int(math.sqrt(x))
# 先在已知質數中找
for p in primes:
if p > n:
return True
if x % p == 0:
return False
# 如果還沒到達根號x，繼續往後面找質數並測試是否能整除 x
for t in range(primes[-1]+1, n+1):
tIsPrime = True
for p in primes:
if(p*p > t):
break
if t % p == 0:
tIsPrime = False
break
if(tIsPrime):
primes.append(t)
if(x % t == 0):
return False
return True
primes = [2]
for x in range(20000002, 1, -1):
status = isPrime(x, primes)
print('{} {}質數'.format(x, '是' if status else '非'))
print('此時primes記錄了 {} 個質數，最後一個質數是 {}'.format(len(primes), primes[-1]))
if(status):
print('找到答案: {}'.format(x))
break
iThome鐵人賽
看影片追技術