iT邦幫忙

0

[已解決] [Python] 找出最接近二千萬的質數?

我的程式碼

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.有錯誤(但我找不出錯在哪裡)
請問大神能幫我除錯嗎?

loukei iT邦新手 5 級 ‧ 2021-08-04 15:10:40 檢舉
可以檢查尾數0,2,4,5,6,8的都可以跳過,這些都可以整除
再來就是加入質數表的概念,嘗試A是否整除的時候從質數表裡面撈
這個[算法](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)是找到一個質數就可以刪除所有衍生的倍數

2 個回答

4
japhenchen
iT邦大師 1 級 ‧ 2021-08-04 12:07:25
最佳解答

用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
看更多先前的回應...收起先前的回應...

平均一個數字只要跑4個for 就結束,負載高的就取平方根的函數

不想要有取平方根的負載的話,你可以把math.sqrt直接換成被測試的數(2~N),但,這比取平方根來測還大量工作,2000萬的平方根是4千多,從4千多到2000萬之間那堆數字,沒意義啊

啊,對了,我忘了說,這個2到平方根的測試方法並未得到完全實證是否為完全可用 (測試到無限大的正整數,沒那麼好的電腦,但在有限資源的環境下測是OK的,還沒找到例外數,我的數學能力只有到小五的程度.. ),如果證實成了可用且高效的算法,記得掛上我的名字就好,但..應該不可能花生

....

淺水員 iT邦高手 3 級 ‧ 2021-08-04 14:54:29 檢舉

只測試到 https://chart.googleapis.com/chart?cht=tx&chl=%5Clog_2%7Bx%7D 的話
一些數字會判斷錯誤喔
例如下列這個會回傳 True

print(isPrime(13*13))

AKS是我在網上找到的一個可能的測試方法,至於是不是可信,也只能交給大家去測試看看了..
13×13=169
2 到 log2(169) → 2 ~ 7 ....... 呃,叭噗~

還是2到平方根的算法比較實在

小魚 iT邦大師 1 級 ‧ 2021-08-04 18:40:42 檢舉

學生時代學的是2~平分根, 其實可以直接單數step -2了..

沒想那麼多,通常偶數在第一個2時就會挑掉了..

1092B0007 iT邦新手 4 級 ‧ 2021-08-05 10:31:54 檢舉

謝謝您的回答

2
淺水員
iT邦高手 3 級 ‧ 2021-08-04 16:20:33

判斷 x 是否為質數,只要確認 x 都不能被「小於等於根號 x 的質數」整除即可

也就是說要判斷二千萬內的質數,可以先找出 https://chart.googleapis.com/chart?cht=tx&chl=%5Csqrt%7B20000000%7D%20%20%5Csimeq%204472.136 以內的所有質數
把它們儲存在一個列表中,後續判斷只要從這些質數來找

下列這個程式是會自動建立質數表,能盡可能減少重複的判斷

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
msn1939 iT邦新手 5 級 ‧ 2021-08-05 07:32:14 檢舉

google. 20000003

1092B0007 iT邦新手 4 級 ‧ 2021-08-05 10:32:04 檢舉

謝謝您的回答

我要發表回答

立即登入回答