Home >Web Front-end >Front-end Q&A >How to find prime numbers within 100 in JavaScript

How to find prime numbers within 100 in JavaScript

PHPz
PHPzOriginal
2023-04-24 10:47:401504browse

JavaScript is a commonly used programming language that provides very powerful functions to solve various problems. In this article, we will explore how to use JavaScript to find prime numbers up to 100.

Prime numbers refer to natural numbers greater than 1 that are not divisible by other natural numbers except 1 and itself. In computer science, solving prime numbers is a very common problem as they play a very important role in fields such as encryption and cryptography. One of the simplest ways to test whether a number is prime is by trial division. The basic idea of ​​trial division is: for each number n to be detected, try to divide n by every number from 2 to n-1. If n cannot be divided, then n is a prime number.

The following is the code to implement this algorithm in JavaScript:

//定义一个函数来检测一个数是否为素数
function isPrime(num) {
  //1和0不是素数
  if (num <= 1) {
    return false;
  }
  //2是素数
  if (num === 2) {
    return true;
  }
  //大于2的偶数不是素数
  if (num % 2 === 0) {
    return false;
  }
  //尝试从3到num-1之间的奇数去整除num
  for (let i = 3; i < num; i += 2) {
    if (num % i === 0) {
      return false;
    }
  }
  //如果都无法整除,那么num就是素数
  return true;
}

//测试函数
for (let i = 1; i <= 100; i++) {
  if (isPrime(i)) {
    console.log(i + "是素数");
  } else {
    console.log(i + "不是素数");
  }
}

In the above code, we first define an isPrime function to detect whether a number is prime. Its specific implementation process is:

  1. If num is less than or equal to 1, then num is not a prime number and false is returned.
  2. If num is equal to 2, then num is a prime number and returns true.
  3. If num is an even number greater than 2, then num is not a prime number and returns false.
  4. Try to divide num with odd numbers from 3 to num-1. If it cannot be divided, num is a prime number and true is returned.
  5. If none of the above conditions are met, then num is not a prime number and false is returned.

Next we use a loop to test whether each number between 1 and 100 is a prime number. If it is a prime number, output the number, otherwise the output is not a prime number.

I won’t show all the output results here, but the running results are all correct.

In actual development, we may need to determine whether a number larger than 100 is a prime number. In this case, using trial division will be very time-consuming because the number of values ​​from 2 to num-1 is very high. Therefore, we need to use more efficient algorithms to determine whether a number is prime. One of the commonly used algorithms is the "Ehrlich sieve method", which can find all prime numbers from 1 to n in a time complexity of O(nloglogn). However, in this article, we only briefly introduce and implement trial division.

The above is the detailed content of How to find prime numbers within 100 in JavaScript. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn