在JavaScript中查詢第n個素數

在本題中，我們的任務是利用JavaScript的功能找到第n個素數。我們將使用兩個函式來解決這個問題。

理解問題

手頭的問題是使用Javascript程式設計找到第n個素數。素數是一個大於1的正整數，除了1和它本身之外沒有其他正因數。任務是建立一個JavaScript函式，該函式接受輸入n。這裡n表示要查詢的素數的位置。

問題的邏輯

為了解決這個問題，我們將採用兩步法。第一步，我們需要定義一個輔助函式來檢查數字是否為素數。在這個函式中，我們將檢查該數字除了1和它本身之外是否還有其他因數。該函式將從2迭代到該數字的平方根，並檢查是否存在任何因數。

在第二步中，我們將定義主函式，藉助它我們將找到第n個素數。在這個函式中，我們將初始化一個計數器變數來跟蹤到目前為止找到的素數的數量。我們將數字初始化為2。我們將使用一個while迴圈進行迭代，直到計數達到n。在迭代過程中，我們將透過呼叫上述函式來檢查該數字是否為素數。如果該數字是素數，那麼我們將增加計數器變數的值。我們將返回數字的值。

演算法

步驟1：因為我們必須找到第n個素數，所以為了完成這項任務，我們將定義一個函式來檢查數字是否是素數。函式的名稱將是isPrime，在函式內部，我們將傳遞一個引數num。

步驟2：在上述函式中，我們將檢查num是否小於或等於1。如果此條件為真，那麼我們將返回false，這意味著該數字不是素數。

步驟3：現在我們將使用一個for迴圈，這個迴圈將執行到Math.sqrt(num)。在這個迴圈中，我們將檢查另一個條件：如果num被當前數字整除且餘數為零，那麼我們將返回false，否則返回true。

步驟4：之後，我們將定義主函式來查詢第n個素數。並將此函式命名為findNthPrime，在這個函式中，我們將傳遞一個引數n。

步驟5：首先，我們將宣告兩個變數count和num，這兩個變數的初始值分別為0和2。

步驟6：因此，在此步驟中，我們將使用一個while迴圈，並執行此迴圈，直到count的值小於n。在這個迴圈中，我們將檢查num是否是素數。如果此條件為真，則將count的值加1。否則，將num的值加1。

步驟7：最後返回最終值num - 1。

示例

//Function to check the number is prime
function isPrime(num) {
   if (num <= 1) {
     return false;
   }
   for (let i = 2; i <= Math.sqrt(num); i++) {
     if (num % i === 0) {
      return false;
     }
   }
   return true;
  }
 
  //Function to find the nth prime number
  function findNthPrime(n) {
   let count = 0;
   let num = 2;
   while (count < n) {
     if (isPrime(num)) {
      count++;
     }
     num++;
   }
   return num - 1;
  }
 
  console.log(findNthPrime(10));
  console.log(findNthPrime(100));

輸出

29
541

複雜度

查詢第n個素數的時間複雜度為O(n * sqrt(num))，其中num是輸入數字，n是素數的位置。這種複雜度的原因為isPrime函式的時間複雜度為O(sqrt(num))，而findNthPrime函式的時間複雜度為O(n * sqrt(num))，因為此函式呼叫了isPrime函式。程式碼的空間複雜度為O(1)，因為程式碼使用少量變數來儲存中間值。

結論

提供的程式碼有效地找到了第n個素數。我們使用了輔助函式來檢查數字是否是素數，還使用了主函式來迭代數字，直到我們找到第n個素數。

更新於：2023年8月14日

4K+ 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告