SOGO論壇

標題: 《質數》 [列印本頁]
作者: Hhy1552    時間: 2022-11-4 13:28:26     標題: 《質數》

本文最後由 Hhy1552 於 2022-11-4 13:42 編輯

公開一下我的代碼：

我在Python的環境中寫了一個程式，如果沒有寫錯的話，應該是可以用來計算質數的。例如：

輸入「lp(100)」就會計算頭100個質數。

輸入「lp(1000)」就會計算頭1000個質數。

輸入「lp(10000)」就會計算頭10000個質數。

「lp」是「list primes」的短寫。

「lp」的代碼是：
  1. def lp(k):
  2.     p=[0]*k
  3.     s=0
  4.     n=2
  5.     while s<k:
  6.         i=0
  7.         while i<s and n%p[i]!=0:
  8.             if p[i]*p[i]>n:
  9.                 i=s
  10.             else:
  11.                 i+=1        
  12.         if i==s:
  13.             p[s]=n
  14.             s+=1
  15.         n+=1
  16.     return p
複製代碼
作者: Hhy1552    時間: 2022-11-4 13:34:42

本文最後由 Hhy1552 於 2022-11-4 13:54 編輯

希望沒有寫錯。測試一下(好像)是可以用。

利用上面的lp函數，可以計算出第100個質數是541；第1000個質數是7919。

lp(100)[-1]，會出541。

lp(1000)[-1]，會出7919。

放上[-1]的意思是說，在那個數列中拿出「從最尾」數過來的第一個。

您也可以選擇拿「從最尾」數過來的第二個。

例如，lp(100)[-2]，會出523。

(背景就是說，第99個質數是523。)

作者: Hhy1552    時間: 2022-11-4 13:49:18

本文最後由 Hhy1552 於 2022-11-4 13:50 編輯

然後，要計算第一百萬個質數，就是輸入：

lp(1000000)[-1]

答案會出：15485863。

而這個在我的電腦上要用1分鐘左右計算。就是60秒左右。
作者: Hhy1552    時間: 2022-11-4 14:19:21

我剛才用上面的這個程式計算了一下第855117個質數。

lp(855117)[-1]

答案給出：13097363。

然後我要試一試lp(78155249)[-1]…

但這個估計要計算超過一個小時。
作者: Hhy1552    時間: 2022-11-4 21:21:49

本文最後由 Hhy1552 於 2022-11-4 21:23 編輯

嗯。還在計算中。

我應該是在今天(2022年11月04日)下午的14時15分左右給電腦開始計算第78155249個質數的。

到剛才，還是在計算中。我也不知道要計算多久。估計可能會是8個小時左右。但我也不肯定。

然後，在今天的時間裡，我也看了這次的那套新電影《獨行月球》。

而昨天，我就看了另一套電影《共助2》。
作者: Hhy1552    時間: 2022-11-5 15:32:11

本文最後由 Hhy1552 於 2022-11-5 15:41 編輯

關於lp(78155249)[-1]的計算：

嗯。昨天，計算到晚上23點的時候，結果還沒有計算出來。我在昨天23點(或左右)的時候把計算停了。

如果要再計算，就得從頭算起。

昨天的計算，是從大約14點15分，到23點00分。結果沒有出來。不過就用了8小時45分鐘左右的計算時間。

然後，今天，做了一些時間測量，我才知道，在一開始的那些數量級別(當k=1000、10000、100000)，k每上升10倍，lp(k)的計算時間會上升大約28倍。

78155249是接近10的8次方。

從今天的測量得知，要計算lp(10000000)，這是10的7次方，得用大約1777秒。

那估計：如果要計算到lp(100000000)，這是10的8次方，得用1777秒的大約31倍。(比28倍大一些。)

1777秒的31倍，是大約15.3小時。

下面是今天的時間測量數據：

k=10 time=0.0(s) na
k=100 time=0.0(s) na
k=1000 time=0.003988742828369141(s) na
k=10000 time=0.08794498443603516(s) ratio= 22.048296473401077
k=100000 time=2.2129108905792236(s) ratio= 25.1624456445124
k=1000000 time=62.05074620246887(s) ratio= 28.040327546233573
k=10000000 time=1777.5864427089691(s) ratio= 28.64730162807039

上面這些數據，是用下面這套程序計算出來的：(總計算時間是30分鐘左右)
  1. import math
  2. import time

  4. def lp(k):
  5.     p=[0]*k
  6.     s=0
  7.     n=2
  8.     while s<k:
  9.         i=0
  10.         while i<s and n%p[i]!=0:
  11.             if p[i]*p[i]>n:
  12.                 i=s
  13.             else:
  14.                 i+=1        
  15.         if i==s:
  16.             p[s]=n
  17.             s+=1
  18.         n+=1
  19.     return p

  21. m=7
  22. b=0
  23. for i in range(0,m):
  24.     k=int(math.pow(10,i+1))
  25.     a=time.time()
  26.     lp(k)
  27.     a=time.time()-a
  28.     if b==0:
  29.         print('k='+str(k),'time='+str(a)+'(s)','na')
  30.     else:
  31.         print('k='+str(k),'time='+str(a)+'(s)','ratio=',a/b)
  32.     b=a
複製代碼
作者: Hhy1552    時間: 2022-11-5 18:08:46

本文最後由 Hhy1552 於 2022-11-5 18:12 編輯

我試了用k=78，780，7800，78000，780000，7800000，這六級來測量一下lp(k)分別的計算時間。

以下是出來的數據：

k=78 time=0.00046539306640625(s) na
k=780 time=0.002991199493408203(s) ratio= 6.427254098360656
k=7800 time=0.06383013725280762(s) ratio= 21.339311334289814
k=78000 time=1.5437488555908203(s) ratio= 24.185266114603525
k=780000 time=43.41979908943176(s) ratio= 28.12620649543039
k=7800000 time=1509.7623586654663(s) ratio= 34.771288451975764

發現到了後來，當從k＝780000提升到ｋ＝7800000，lp(k)的計算時間會提升了34倍左右。

如果再升一級時，計算時間要提升42倍的話，那計算lp(78155249)的時間可能會到了:

1509  (秒) x 42 = 63378 (秒) ＝ 17.605(小時)。
作者: Hhy1552    時間: 2022-11-5 20:55:13

我找到一個可能可行的方案。不過我應該不會今天晚上弄。晚上應該休息。

這個方案就是用Go(一種程序語言)來寫類似最上面的那個計算質數的程序。

我在網絡上看到說，Go比Python會快40倍。如果真的如此，那就有希望可以在一個小時的計算時間內計算出第78155249個質數。

但我還不太會Go。如果要做的話，得研究研究。
作者: Hhy1552    時間: 2022-11-6 12:26:59

禮拜日。2022年11月06日。

天氣有點冷。在夢中我夢見自己飛，還好像可以控制水。

我今天中午剛剛下載並安裝了Go的1.19.3版。

以前，我是有安裝過Go(應該是以前的版本)，但是我很少用，也沒有學習到很多關於如何用Go。

今天，我想下午去去海洋公園，看看動物。明天，我又有事。

可能後天研究研究Go。



歡迎光臨 SOGO論壇 (https://oursogo.com/) Powered by OURSOGO.COM