您正在使用新版介面(Beta)。返回原版介面

本頁面由機器翻譯自動翻譯而成,翻譯內容可能存在不準確之處,敬請見諒。

keisan服務於日常生活和工作的高精度計算網站

列舉不超過100萬的質數

作者: ameya執行次數: 13362

※ 本程式庫由會員建立。本站不對其內容負責。

管理書籤
可透過埃拉托斯特尼篩法顯示100萬以內的質數。
從 2 開始
之間的所有質數。
我使用了所謂的「Wheel Sieve」這種加速技術。大概吧。
雖然我沒能完全理解英文的解說,但根據維基百科上的圖片推斷,試著隨意組裝了一下。

/* 首先從 2*3*5*7=210 內的自然數中,排除 2、3、5、7 的倍數,準備一個名為 Wheel 的陣列。由於處理的關係,陣列範圍延伸至 211,但這只是「210+1」,而它剛好是下一個質數,純屬巧合。 */
numeric wheel[] = {1,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,121,127,131,137,139,143,149,151,157,163,167,169,173,179,181,187,191,193,197,199,209,211};
/* Wheel 的元素數為 */
whlen = 48;
/* 準備一個包含差分(的 1/2)的陣列(因實際需求,起始位置偏移了 1。由於旋轉處理較為繁瑣,因此包含兩輪的資料)*/
numeric ntb105[] = {1,2,1,2,3,1,3,2,1,2,3,3,1,3,2,1,3,2,3,4,2,1,2,1,2,4,3,2,3,1,2,3,1,3,3,2,1,2,3,1,3,2,1,2,1,5,1,5,1,2,1,2,3,1,3,2,1,2,3,3,1,3,2,1,3,2,3,4,2,1,2,1,2,4,3,2,3,1,2,3,1,3,3,2,1,2,3,1,3,2,1,2,1,5,1,5};
/* 也建立一個用以從篩網索引減去輪盤上位置的表格 */
numeric nrev105[105];
for (k = 1; k <= whlen; k = k + 1) {
  nrev105[(wheel[k] - 3) / 2] = k - 1;
}
/* 接下來就隨意轉動之類的 */
numeric numx[48];
idx = 4;
while (idx < enphsiev) {
  for (z = 0; z < whlen; z = z + 1) {
    if (sieve[idx] == 0) {
      m = nrev105[mod(idx, 105)];    /* 輪盤起始位置 */
      num = idx * 2 + 3;         /* 此公式將 sieve 的索引轉換為實際數值 */
      j = ((num * num) - 3) / 2;     /* 這是將平方值逆轉換回索引 */
      for (k = 0; k < whlen; k = k + 1) {
        numx[k] = ntb105[m + k] * num; /* 由於乘法運算耗時,故預先建立查表 */
      }
      while (j < sievemax) {      /* 篩法的主迴圈 */
        for (k = 0; k < whlen; k = k + 1) {
          sieve[j] = 1;
          j = j + numx[k];
        }
      }
    }
    idx = idx + ntb105[z];
    if (idx >= enphsiev) {break;}
  }
}
※篩陣列 sieve[idx] 的對應關係如下:idx=0 → 3,idx=1 → 5,idx=2 → 7。
※順帶一提,在主迴圈中,sieve[j] 的參數 j 最多會超過 maxsieve 達 whlen-1 次,因此需要採取某種對策。
※要完成程式,還需要以下這段程式碼以及顯示結果的處理程序。
/* 假設輸入變數為 UpperLimit */
sievemax = ceiling(UpperLimit / 2);
enphsiev = int(sqrt(UpperLimit) / 2);
/* 輸入數值在變更前似乎會被視為常數,因此可用於陣列的參數 */
numeric sieve[UpperLimit];

目前還沒有關於此計算的用戶評價。