在 JavaScript 中查找第 n 个素数

javascriptweb developmentfront end technologyobject oriented programming更新于 2024/12/9 0:44:17

在给定的问题陈述中，我们的任务是借助 Javascript 功能查找第 n 个素数。因此，我们将使用两个函数来解决这个问题。

理解问题

当前的问题是使用 Javascript 编程查找第 n 个素数。因此，素数是一个大于 1 的正整数，并且除了 1 和数字本身之外没有其他正因数。任务是创建一个接受输入 n 的 Javascript 函数。这里 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 isPrime(num) {
   if (num <= 1) {
     return false;
   }
   for (let i = 2; i <= Math.sqrt(num); i++) {
     if (num % i === 0) {
      return false;
     }
   }
   return true;
  }
 
  //查找第 n 个素数的函数
  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)，因为代码使用一些变量来存储中间值。