Merge pull request #351 from JimmyJoo/master

raklaptudirm · web-flow · commit 38a5cb297a24 · 2021-05-23T13:29:22.000+05:30
Improved SieveOfEratosthenes.js
diff --git a/Maths/SieveOfEratosthenes.js b/Maths/SieveOfEratosthenes.js
@@ -10,7 +10,15 @@ const sieveOfEratosthenes = (n) => {
   const sqrtn = Math.ceil(Math.sqrt(n))
   for (let i = 2; i <= sqrtn; i++) {
     if (primes[i]) {
-      for (let j = 2 * i; j <= n; j += i) {
+      for (let j = i * i; j <= n; j += i) {
+        /*
+        Optimization.
+        Let j start from i * i, not 2 * i, because smaller multiples of i have been marked false.
+
+        For example, let i = 4.
+        We do not have to check from 8(4 * 2) to 12(4 * 3)
+        because they have been already marked false when i=2 and i=3.
+        */
         primes[j] = false
       }
     }
