算法：打印第n個連續的素數

Question

我目前正在學習算法，並且遇到了面試官關於按順序打印出第n個素數的函數的代碼挑戰。因此，這將是這樣的：

getPrimeNth(10)將打印1 2 3 5 7 11 13 17 19 23

，但最讓我發現打印出只是第n個號，所以23，或者只是那些如果是素數，將檢測到的人的。我將冒風險爲此，但我似乎無法找到正確的解決方案。

Answer 1

對於初學者來說，一個不是首要的。

其次，你的問題需要進一步澄清....

素數是沒有挑戰性 - 有大量的可用信息。

最簡單的解決方案是簡單地通過修改該數字的平方根來測試每個數字。如果它變爲零，它不是素數。將素數一個接一個地存儲在一個數組中。我不會直接向你提供答案，但請閱讀更多有關埃拉託斯通斯篩 - 這是IMO非常低效，但你必須從哪裏開始。

因此，所述第一原將在時隙0，第二次在時隙1，等等，等等

Answer 2

下面的代碼試圖尋找並節省高達N的所有可能的素數（由宏定義）。它只是調用效用函數is_prime()，它檢查給定的數字是否爲素數。

#define TRUE 1 
#define FALSE 0 
#define N 10 

typedef short int bool; 

bool is_prime(int num) 
{ 
    int i = 2; 

    for (i = 2; i <= (num - 1); i++) { 
     if ((num % i) == 0) { 
      return FALSE; 
     } 
    } 
    return TRUE; 
} 


int main() 
{ 
    int primes[N]; 
    int num_primes = 0; 
    int num = 2; /* start with 2 */ 

    while (num_primes != N) { 
     if (is_prime (num) == TRUE) { 
      primes[num_primes] = num; 
      num_primes++; 
     } 
     num++; 
    } 

    int i = 0; 
    for (i = 0; i < N; i++) { 
     printf ("%d ", primes[i]); 
    } 
    printf ("\n"); 

} 

輸出：2 3 5 7 11 13 17 19 23 29