Advertisement
stanevplamen

Prime SieveOfEratosthenes

Sep 27th, 2022
857
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Javascript program to check Euclid Number
  2. var MAX = 10000;
  3. var arr = [];
  4.  
  5. // Function to generate prime numbers
  6. function SieveOfEratosthenes()
  7. {
  8.  
  9.     // Create a boolean array "prime[0..n]" and initialize
  10.     // all entries it as true. A value in prime[i] will
  11.     // finally be false if i is Not a prime, else true.
  12.     var prime = Array(MAX).fill(true);;
  13.  
  14.     for (var p = 2; p * p < MAX; p++) {
  15.         // If prime[p] is not changed, then it is a prime
  16.  
  17.         if (prime[p] == true) {
  18.  
  19.             // Update all multiples of p
  20.             for (var i = p * 2; i < MAX; i += p)
  21.                 prime[i] = false;
  22.         }
  23.     }
  24.  
  25.     // store all prime numbers
  26.     // to vector 'arr'
  27.     for (var p = 2; p < MAX; p++)
  28.         if (prime[p])
  29.             arr.push(p);
  30. }
  31.  
  32. // Function to check the number for Euclid Number
  33. function isEuclid( n)
  34. {
  35.  
  36.     var product = 1;
  37.     var i = 0;
  38.  
  39.     while (product < n) {
  40.  
  41.         // Multiply next prime number
  42.         // and check if product + 1 = n
  43.         // holds or not
  44.         product = product * arr[i];
  45.  
  46.         if (product + 1 == n)
  47.             return true;
  48.  
  49.         i++;
  50.     }
  51.  
  52.     return false;
  53. }
  54.  
  55. // Driver code
  56.  
  57. // Get the prime numbers
  58. debugger;
  59. SieveOfEratosthenes();
  60.  
  61. // Get n
  62. var n = 31;
  63.  
  64. // Check if n is Euclid Number
  65. if (isEuclid(n))
  66.     document.write("YES<br>");
  67. else
  68.     document.write("NO<br>");
  69.      
  70. // Get n
  71. n = 42;
  72.  
  73. // Check if n is Euclid Number
  74. if (isEuclid(n))
  75.     document.write("YES<br>");
  76. else
  77.     document.write("NO<br>");
  78.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement