วิธีสร้างเลขเฉพาะ (Prime Numbers) ใน JavaScript

สร้างเลขเฉพาะ (Prime numbers) ด้วย nested loop ตรวจสอบหารลงตัว

ตัวอย่าง: เลขเฉพาะ 1-20

<html>
  <head>
    <title>JavaScript Prime</title>
  </head>
  <body>
    <script>
      for (var limit = 1; limit <= 20; limit++) {
        var isPrime = true;
        for (var i = 2; i <= Math.sqrt(limit); i++) {
          if (limit % i === 0) {
            isPrime = false;
            break;
          }
        }
        if (isPrime && limit > 1) {
          document.write("<br>" + limit);
        }
      }
    </script>
  </body>
</html>

ผลลัพธ์

2
3
5
7
11
13
17
19

การปรับปรุงประสิทธิภาพ (Optimization)

• ลูปในแค่ Math.sqrt(limit) แทน limit (ลด complexity จาก O(n²) เป็น O(n√n))
• ข้ามเลขคู่ (ยกเว้น 2)
• ใช้ Sieve of Eratosthenes สำหรับหา primes มากๆ

Sieve of Eratosthenes (หา primes ≤ n)

function sieveOfEratosthenes(n) {
  var primes = [];
  var isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
  
  for (var i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      for (var j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  
  for (var i = 2; i <= n; i++) {
    if (isPrime[i]) primes.push(i);
  }
  return primes;
}

console.log(sieveOfEratosthenes(100));
// [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

ฟังก์ชันตรวจสอบ Prime เดียว

function isPrime(num) {
  if (num <= 1) return false;
  if (num <= 3) return true;
  if (num % 2 === 0 || num % 3 === 0) return false;
  for (var i = 5; i * i <= num; i += 6) {
    if (num % i === 0 || num % (i + 2) === 0) return false;
  }
  return true;
}