這次我們要用昨天學到的佇列搭配一個叫做埃拉托斯特尼篩法的東西去找出一定範圍的質數。

埃拉托斯特尼篩法的維基百科介紹:
https://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95

簡單的說，假設要找100內的質數，我們就先用2去做篩選，2先判定為質數，而2的倍數全部從100內的數字刪除，再用3去做篩選，3先判定為質數，而3的倍數全部從100內的數字刪除...不斷持續篩選，最後保留的數就都是質數。

了解之後，我們就來寫寫程式吧!
先沿用昨天實作佇列的程式碼，不過這次多了記錄佇列的大小程式碼在建構子內

class QueueNode {
  constructor(data, next) {
    this.data = data
    this.next = next
  }
}

class Queue {
  constructor() {
    this.front = null
    this.tail = null
    this.size = 0
  }

  isEmpty() {
    return this.front === null
  }

  enqueue(value) {
    this.size++
    let node = new QueueNode(value)
    if (this.isEmpty()) {
      this.front = node
      this.tail = node
    } else {
      // 讓尾巴節點先指向node新節點
      this.tail.next = node
      // 讓新節點變成新的尾巴節點
      this.tail = node
    }
  }

  dequeue() {
    this.size--
    let result = this.front.data
    if (this.isEmpty()) {
      return null
    }

    if (this.front === this.tail) {
      this.front = null
      this.tail = null
    } else {
      // 使原本前面第二個節點變成第一個節點
      this.front = this.front.next
    }

    return result
  }
}

接著我們定義一個函式 primesUpToN，並建立佇列 qq，裡面包含了要判斷是否為質數的數字們，另一個空佇列 q2，及記錄質數的陣列 primes

function primesUpToN(n) {
  let primes = [];
  let qq = new Queue();
  let q2 = new Queue();

  for (let i = 2; i < n; i++) {
    qq.enqueue(i);
  }
}

接下來需要一些思考邏輯，在這裡我們需要對每個數進行判斷，可見需要使用迴圈，在不斷重複判斷2,3,5...的倍數情況下，適合用 while，只要 qq 這個佇列裡還有任何數字，就要繼續判斷下去

然後在迴圈內，將第一個質數2取出，放到 primes 陣列內，待會要用此質數去除 qq 全部的數

function primesUpToN(n) {
  let qq = new Queue();
  let primes = [];
  let q2 = new Queue();

  for (let i = 2; i < n; i++) {
    qq.enqueue(i);
  }

  // 當qq裡面還有任何數字，就不斷執行下去
  while (qq.size >= 1) {
    let prime = qq.dequeue();
    primes.push(prime);
  }
}

再次在 while 迴圈建立一個 while 迴圈，將 qq 內的數字用已記錄的質數全部除過一遍，不是質數倍數的數字放進 q2 內，最後將 q2 內容傳給 qq ，再讓外層迴圈執行數次。

function primesUpToN(n) {
  let qq = new Queue();
  let primes = [];
  let q2 = new Queue();

  for (let i = 2; i < n; i++) {
    qq.enqueue(i);
  }

  // 當qq裡面還有任何數字，就不斷執行下去
  while (qq.size >= 1) {
    let prime = qq.dequeue();
    primes.push(prime);

    // 全部的數字都判斷過一次
    while (qq.size > 0) {
      let num = qq.dequeue()
      // 不是質數的倍數就推入 q2
      if (num % prime !== 0) {
        q2.enqueue(num)
      }
    }
    
    // 將qq和q2作交換
    let temp = qq // 此行的qq為空佇列
    qq = q2 // qq此時為篩過的佇列
    q2 = temp // q2又變成空佇列
  }
  return primes
}

等待迴圈結束後，回傳的陣列其數字就都是質數啦~

這次的程式碼在以下連結，可以參考看看:
https://github.com/a90100/javascript-data-structure/blob/master/dya9-queue-prime-number.js

明天我們將會來介紹遞迴，並搭配一個問題來現學現賣!