Guest User

bit-sieve

a guest
Apr 4th, 2022
42
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
HTML 5 2.06 KB | None | 0 0
  1. <!--
  2. An implementation of Sieve of Eratosthenes using a bit array
  3. Author: Nguyen Thanh Do
  4. -->
  5. <!DOCTYPE html>
  6. <html>
  7.     <head>
  8.         <title>Sieve of Eratosthenes</title>
  9.     </head>
  10.     <body>
  11.         <h3>Sieve of Eratosthenes</h3>
  12.         <input type="number" id="input-number">
  13.         <p>Click the button to submit the limit</p>
  14.         <button onclick="show()">Submit</button>
  15.         <p id="output-intro"> </p>
  16.         <p id="output-numbers"></p>
  17.     </body>
  18.     <script>
  19.         let limit;
  20.         let result;
  21.         let sentence;
  22.         let marked;
  23.         const masks = [1, 2, 4, 8, 16, 32, 64, 128];
  24.        
  25.         function getInput() {
  26.             limit = document.getElementById("input-number").value;
  27.         }
  28.  
  29.         function markNotPrime(num) {
  30.             let idx = Math.floor(num / 8);
  31.             marked[idx] |= masks[num % 8];
  32.         }
  33.  
  34.         function isNotPrime(num) {
  35.             let idx = Math.floor(num / 8);
  36.             return marked[idx] & masks[num % 8];
  37.         }
  38.  
  39.         function markNumbers() {
  40.             marked = new Uint8Array(Math.floor(limit / 8) + 1).fill(0);
  41.  
  42.             markNotPrime(0);
  43.             markNotPrime(1);
  44.  
  45.             for (let num = 4; num <= limit; num += 2)
  46.                 markNotPrime(num);
  47.  
  48.             for (let num = 3; num <= Math.sqrt(limit); num += 2) {
  49.                 if (isNotPrime(num) == 0) {
  50.                     for (let mul = num * num; mul <= limit; mul += num * 2)
  51.                         markNotPrime(mul);
  52.                 }
  53.             }
  54.         }
  55.  
  56.         function printPrimes() {
  57.             sentence = "List of prime numbers from 1 to " + (String(limit) + ": ");
  58.             result = '';
  59.    
  60.             for (let num = 0; num <= limit; num++) {
  61.                 if (isNotPrime(num) == 0)
  62.                     result += (String(num) + ' ');
  63.             }
  64.  
  65.             document.getElementById("output-intro").innerHTML = sentence;
  66.             document.getElementById("output-numbers").innerHTML = result;  
  67.         }
  68.        
  69.         function noPrime() {
  70.             sentence = "There is no prime number. Please enter a number greater than or equal to 2";
  71.             result = '';
  72.  
  73.             document.getElementById("output-intro").innerHTML = sentence;
  74.             document.getElementById("output-numbers").innerHTML = result;  
  75.         }
  76.        
  77.         function show() {
  78.             getInput();
  79.        
  80.             if (limit < 2) {
  81.                 noPrime();
  82.             }
  83.             else {
  84.                 markNumbers();
  85.                 printPrimes();
  86.             }
  87.         }
  88.     </script>
  89. </html>
  90.  
Advertisement
Add Comment
Please, Sign In to add comment