《質數》

Hhy1552

公開一下我的代碼：

我在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

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

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

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

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

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

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

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

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

Hhy1552

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

lp(1000000)[-1]

答案會出：15485863。

而這個在我的電腦上要用1分鐘左右計算。就是60秒左右。

Hhy1552

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

lp(855117)[-1]

答案給出：13097363。

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

但這個估計要計算超過一個小時。

Hhy1552

嗯。還在計算中。

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

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

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

而昨天，我就看了另一套電影《共助2》。

Hhy1552

關於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
   
3. 
   
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
    
20. 
    
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

我試了用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

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

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

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

但我還不太會Go。如果要做的話，得研究研究。

Hhy1552

禮拜日。2022年11月06日。

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

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

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

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

可能後天研究研究Go。