使用#pragma omp進行硬性並行化以找到第N個素數

Question

此問題的目標是能夠獲得2.000.000個第一素數並能夠確定哪個是第2000000個素數。

我們從這個代碼開始：

#include <stdlib.h> 
#include <stdio.h> 

#define N 2000000 

int p[N]; 

main(int na,char* arg[]) 
{ 
int i; 
int pp,num; 

printf("Number of primes to find: %d\n",N); 

p[0] = 2; 
p[1] = 3; 
pp = 2; 
num = 5; 

while (pp < N) 
{ 
    for (i=1; p[i]*p[i] <= num ;i++) 
    if (num % p[i] == 0) break; 
    if (p[i]*p[i] > num) p[pp++]=num; 
    num += 2; 
} 

printf("The %d prime is: %d\n",N,p[N-1]); 
exit(0); 
} 

現在我們被要求使這個過程通過編譯OMP線程。這是我到目前爲止所做的：

#include <stdlib.h> 
#include <stdio.h> 

#define N 2000000 
#define D 1415 

int p[N]; 
main(int na,char* arg[]) 
{ 
int i,j; 
int pp,num; 

printf("Number of primes to find: %d\n",N); 

p[0] = 2; 
p[1] = 3; 

pp = 2; 
num = 5; 

while (pp < D) 
{ 
    for (i=1; p[i]*p[i] <= num ;i++) 
     if (num % p[i] == 0) break; 
    if (p[i]*p[i] > num) p[pp++]=num; 
    num += 2; 
} 

int success = 0; 
int t_num; 
int temp_num = num; 
int total = pp; 

#pragma omp parallel num_threads(4) private(j, t_num, num, success) 
{ 
    t_num = omp_get_thread_num(); 
    num = temp_num + t_num*2; 

    #pragma omp for ordered schedule(static,4) 
    for(pp=D; pp<N; pp++) { 
     success = 0; 
     while(success==0) { 
      for (i=1; p[i]*p[i] <= num;i++) { 
       if (num % p[i] == 0) break; 
      } 
      if (p[i]*p[i] > num) { 
       p[pp] = num; 
       success=1; 
      } 
      num+=8; 
     } 

    } 
} 

//sort(p, 0, N); 

printf("El %d primer es: %d\n",N,p[N-1]); 

exit(0); 
} 

現在讓我解釋我的「部分」解決方案，因此，我的問題。

第一個D素數是用序列碼獲得的，所以現在我可以檢查大數的可分性。

每個線程運行素數的對角線，以便線程之間不存在依賴關係，並且不需要同步。但是，這種方法的問題如下：

1. 一個線程可能會比另一個線程
2. 作爲問題1.直接後果產生更多的素數，它會產生N個素數，但他們不會被訂購，所以當主要計數器'pp'達到'N'時，最後一個素數不是第2000000個素數，這是更高級的素數。
3. 它也可能是當它產生2.000.000個素數的時候，能夠達到真正的2.000.000th素數的線程可能沒有足夠的時間來把它放在素數組'p'上。

而問題/困境是：

我如何能夠產生2.000.000th素時，知道嗎？

提示： 有人告訴我應該批量（比方說）10.000候選人素數。然後當我不知道發生的事情時，我會知道最後一批10.000個候選人包含2000萬個素數，我可以用快速排序對它進行排序。

我希望我明確自己，這是真正的鍛鍊，我只是試了幾天不停。

Answer 1

我可以想到兩種方法。

1. 一旦你得到了200萬輛總理候選人，你的線程繼續計算，直到你有沒有遺漏的素數是比你低的候選人素數。然後，您可以對素數列表進行排序並從中獲得200萬分之一。

2. 如果您的線程正在生成連續素數的塊，他們應該分別維護塊，然後可以將素數塊隨後重新組合爲主列表。一旦找到第二百萬個素數，重組的線程就可以終止程序。

Answer 2

如果您只需要2000000個素數，則可以維護一個〜4.1MB大小的位陣列並在其上爲每個找到的素數翻轉位。不需要排序。通過實施僅賠率表示方案來減少你的bitarray大小。

分段使用Sieve of Eratosthenes，大小與sqrt(top_value_of_range)（或類似的內容 - 目標是在每個分段上執行大致相同的工作量）成比例。對於n=2000000,n*(log n + log(log n)) == 34366806,prime[771]^2 == 34421689（0爲基礎），所以，預計算第771個奇素數。

每個工作人員也可以計數，因爲它會翻轉這些位，所以當它們全部完成時，您將知道每個範圍的計數，並且只需要掃描包含第2mln個素數的一個範圍，即可最後，找到那個素數。或者讓每個工作人員根據其範圍維護自己的位子 - 你只需要保留一個，並且可以丟棄其他人。

計數的埃拉托色尼篩僞代碼：

Input: an integer n > 1 

Let A be an array of bool values, indexed by integers 3, 5, ... upto n, 
initially all set to true. 

count := floor((n-1)/2) 
for i = 3, 5, 7, ..., while i^2 ≤ n: 
    if A[i] is true: 
    for j = i^2, i^2 + 2i, i^2 + 4i, ..., while j ≤ n: 
     if A[j] is true: 
     A[j] := false 
     count := count - 1 

Now all 'i's such that A[i] is true are prime, 
and 'count' is the total count of odd primes found.