How to find prime numbers between 0 - 100

Question

In Javascript how would i find prime numbers between 0 - 100  i have thought about it  and i am not sure how to find them  i thought about doing x   x but i found the obvious problem with that  this is what i have so far  but unfortunately it is the worst code ever   var prime   function     var num  for  num   0  num  lt  101  num         if  num   2     0           break            else if  num   3     0           break            else if  num   4    0           break            else if  num   5     0           break            else if  num   6     0           break            else if  num   7     0           break            else if  num   8     0           break            else if  num   9     0           break            else if  num   10     0           break            else if  num   11     0           break            else if  num   12     0           break            else           return num             console log prime

User · Answer

Here s an example of a sieve implementation in JavaScript   function getPrimes max        var sieve       i  j  primes           for  i   2  i  lt   max    i            if   sieve i                    i has not been marked -- it is prime             primes push i               for  j   i  lt  lt  1  j  lt   max  j    i                    sieve j    true                                    return primes      Then getPrimes 100  will return an array of all primes between 2 and 100  inclusive   Of course  due to memory constraints  you can t use this with large arguments   A Java implementation would look very similar

User · Answer

Using Sieve of Eratosthenes  source on Rosettacode  fastest solution  https   repl it  caub getPrimes-bench   x000D   x000D  function getPrimes limit    x000D      if  limit  lt  2  return     x000D      var sqrtlmt   limit   5 - 2  x000D      var nums   Array from  length  limit-1      i   gt i 2   x000D      for  var i   0  i  lt   sqrtlmt  i      x000D          var p   nums i  x000D          if  p    x000D              for  var j   p   p - 2  j  lt  nums length  j    p  x000D                  nums j    0  x000D            x000D        x000D      return nums filter x   gt  x      return non 0 values x000D    x000D  document body innerHTML     lt pre style  white-space pre-wrap  gt   getPrimes 100  join        lt  pre gt    x000D   x000D     for fun  this fantasist regexp way  very inefficient   x000D     Array from  length 101      i   gt i  filter n   gt  n gt 1 amp  amp     oo   1    test  o  repeat n   x000D   x000D   x000D

User · Answer

Use following function to find out prime numbers        function primeNumbers         var p     var n   document primeForm primeText value     var d     var x     var prime     var displayAll   2           for  p   3  p  lt   n  p   p   2            x   Math sqrt p          prime   1         for  d   3  prime  amp  amp   d  lt   x   d   d   2          if   p   d     0  prime   0         else prime   1         if  prime    1                displayAll   displayAll   p                           document primeForm primeArea value   displayAll

User · Answer

Whatever the language  one of the best and most accessible ways of finding primes within a range is using a sieve   Not going to give you code  but this is a good starting point   For a small range  such as yours  the most efficient would be pre-computing the numbers

User · Answer

Sieve of Eratosthenes  its  bit look but its simple and it works     function count prime arg         arg   typeof arg      undefined    arg   20    default value     var list    2      var list2    0 1      var real prime           counter   2     while  counter  lt  arg             if  counter   2     0                list push counter                    counter              for  i   0  i  lt  list length - 1  i              var a   list i          for  j   0  j  lt  list length - 1  j                  if  list j    a     0  amp  amp  list j      a                    list j    false           assign false to non-prime numbers                                 if  list i      false                 real prime push list i        save all prime numbers in new array                    window onload count prime 100

User · Answer

function isPrime num      for var i   2  i  lt  num  i        if num   i     0  return false    return num     function primes n     var array of primes     for var i   2  i  lt  n  i         if isPrime i   array of primes push i  gt 1            return array of primes    document write primes 10000

User · Answer

lt html gt   lt head gt   lt script type  text javascript  gt  function primeNumber      x document getElementById  txt field   value    for  i 1  i lt  parseInt x   i        var flag 0 flag1 0       for  j 2  j lt i  j            if i j  0          flag 1        if i  x         flag1 1                   if flag  0      document write i   lt br gt            if flag1  0       document write  Its a prime number        else      document write  Its not a prime number        lt  script gt   lt  head gt    lt body gt    lt input id  txt field  type  text  name  field    gt    lt input type  button  name  submit  value  Submit  onclick  primeNumber       gt   lt  body gt   lt  html gt

User · Answer

Why try deleting by 4  and 6 8 10 12  if we ve already tried deleting by 2   Why try deleting by 9 if  we ve already tried deleting by 3   Why try deleting by 11 if 11   11   121 which is greater than 100   Why try deleting any odd number by 2 at all  Why try deleting any even number above 2 by anything at all    Eliminate the dead tests and you ll get yourself a good code  testing for primes below 100    And your code is very far from being the worst code ever  Many many others would try dividing 100 by 99  But the absolute champion would generate all products of 2  96 with 2  96 to test whether 97 is among them  That one really is astonishingly inefficient    Sieve of Eratosthenes of course is much better  and you can have one -- under 100 -- with no arrays of booleans  and no divisions too     console log 2  var m3   9  m5   25  m7   49  i   3 for    i  lt  100  i    2         if  i    m3  amp  amp  i    m5  amp  amp  i    m7  console log i      else               if  i    m3   m3    6         if  i    m5   m5    10         if  i    m7   m7    14          DONE      This is the sieve of Eratosthenes  were we skip over the composites - and that s what this code is doing  The timing of generation of composites and of skipping over them  by checking for equality  is mixed into one timeline  The usual sieve first generates composites and marks them in an array  then sweeps the array  Here the two stages are mashed into one  to avoid having to use any array at all  this only works because we know the top limit s square root - 10 - in advance and use only primes below it  viz  3 5 7 - with 2 s multiples  i e  evens  implicitly skipped over in advance    In other words this is an incremental sieve of Eratosthenes and m3  m5  m7 form an implicit priority queue of the multiples of primes 3  5  and 7

User · Answer

You can try this method also  this one is basic but easy to understand    var tw   2  th   3  fv   5  se   7     document write tw         th        fv         se           for var n   0  n  lt   100  n         if  n   tw     0   amp  amp   n   th    0   amp  amp   n   fv    0    amp  amp   n   se    0              if  n    1                    continue               document write n

User · Answer

Here is the live demo of this script  http   jsfiddle net K2QJp   First  make a function that will test if a single number is prime or not  If you want to extend the Number object you may  but I decided to just keep the code as simple as possible   function isPrime num        if num  lt  2  return false      for  var i   2  i  lt  num  i              if num i  0              return false            return true      This script goes through every number between 2 and 1 less than the number and tests if there is any number in which there is no remainder if you divide the number by the increment  If there is any without a remainder  it is not prime  If the number is less than 2  it is not prime  Otherwise  it is prime   Then make a for loop to loop through the numbers 0 to 100 and test each number with that function  If it is prime  output the number to the log   for var i   0  i  lt  100  i         if isPrime i   console log i

User · Answer

var n 100              var counter   0              var primeNumbers    Prime Numbers                 for var i 2  i lt  n    i                                counter 0                  for var j 2  j lt  n    j                                        if i gt  j  amp  amp  i j    0                                                  counter                                                           if counter    1                                                primeNumbers   primeNumbers   i                                                          console log primeNumbers

User · Answer

Here s my stab at it   Change the initial i 0 from 0 to whatever you want  and the the second i lt 100 from 100 to whatever to get primes in a different range   for var i 0  i lt 100  i         var devisableCount   2          for var x 0  x lt  i 2  x                 if i     1  amp  amp  i     0  amp  amp  i     x                   if i x     0                      devisableCount                                                   if devisableCount     3           console log i             I tried it with 10000000 - it takes some time but appears to be accurate

User · Answer

check the number is prime or not with JS function  function isPrime num                        var flag   true              for var i 2  i lt  Math ceil num 2   i                                  if  num i   0                                        flag   false                      break                                              return flag

User · Answer

Did anyone try this  It s simple and efficient      function Prime num      if  num  lt   2 return false    for var i   2  i  lt  num  i         if  num   i    0  return false        return true     function PrimeWithin userinput     for var i   2  i  lt  userinput  i         if Prime i            console log i                PrimeWithin 500

User · Answer

It would behoove you  if you re going to use any of the gazillion algorithms that you re going to be presented with in this thread  to learn to memoize some of them    See Interview question   What is the fastest way to generate prime number recursively

User · Answer

A number is a prime if it is not divisible by other primes lower than the number in question   So this builds up a primes array  Tests each new odd candidate n for division against existing found primes lower than n  As an optimization it does not consider even numbers and prepends 2 as a final step    var primes       for var n 3 n lt  100 n  2      if primes every function prime  return n prime  0          primes push n         primes unshift 2

User · Answer

Here s the fastest way to calculate primes in JavaScript  based on the previous prime value   function nextPrime value        if  value  gt  2            var i  q          do               i   3              value    2              q   Math floor Math sqrt value                while  i  lt   q  amp  amp  value   i                    i    2                          while  i  lt   q           return value            return value     2   3   2      Test  var value   0  result       for  var i   0  i  lt  10  i          value   nextPrime value       result push value     console log  Primes    result     Output  Primes    2  3  5  7  11  13  17  19  23  29     It is faster than other alternatives published here  because    It aligns the loop limit to an integer  which works way faster  It uses a shorter iteration loop  skipping even numbers    It can give you the first 100 000 primes in about 130ms  or the first 1m primes in about 4 seconds    x000D   x000D   function nextPrime value    x000D          if  value  gt  2    x000D              var i  q  x000D              do   x000D                  i   3  x000D                  value    2  x000D                  q   Math floor Math sqrt value    x000D                  while  i  lt   q  amp  amp  value   i    x000D                      i    2  x000D                    x000D                while  i  lt   q   x000D              return value  x000D            x000D          return value     2   3   2  x000D        x000D   x000D      var value  result       x000D      for  var i   0  i  lt  10  i      x000D          value   nextPrime value   x000D          result push value   x000D        x000D   x000D      display  Primes      result join         x000D   x000D      function display msg    x000D          document body insertAdjacentHTML  x000D               beforeend   x000D                lt p gt     msg     lt  p gt   x000D             x000D        x000D   x000D   x000D

User · Answer

public static void main String   args        int m   100      int a    new int m       for  int i 2  i lt m  i            for  int j 0  j lt m  j  i              a j         for  int i 0  i lt m  i            if  a i   1  System out println i

User · Answer

This is my solution    find all prime numbers function showMePrimeNumbers start  end       var primes           for var number   start  number  lt  end  number             var primeNumberDividers         there should only be 2  1  amp  number         for var divider   1  divider  lt   number  divider                 if number   divider     0                   primeNumberDividers push divider                                         if primeNumberDividers length     2               primes push number                       return primes     console log showMePrimeNumbers 1  100

User · Answer

Here s how I solved it  Rewrote it from Java to JavaScript  so excuse me if there s a syntax error       function isPrime  n        if  n  lt  2  return false                  An integer is prime if it is not divisible by any prime less than or equal to its square root               var q   Math floor Math sqrt n         for  var i   2  i  lt   q  i                  if  n   i    0                        return false                       return true      A number  n  is a prime if it isn t divisible by any other number other than by 1 and itself  Also  it s sufficient to check the numbers  2  sqrt n

User · Answer

Here is an efficient  short solution using JS generators  JSfiddle  x000D   x000D     Consecutive integers let nats   function   n        while  true  yield n         Wrapper generator let primes   function           yield  sieve primes    nats 2         The sieve itself  only tests primes up to sqrt n  let sieve   function   pg  ng        yield ng next   value      let n  p   pg next   value      while   n   ng next   value   lt  p   p  yield n      yield  sieve pg   function               while  n   ng next   value  if  n   p  yield n                 Longest prefix of stream where some predicate holds let take   function   vs  fn        let nx      while    nx   vs next    done  amp  amp  fn nx value   yield nx value    document querySelectorAll  dd   0  textContent       Primes smaller than 100         take primes    x   gt  x  lt  100   join       x000D   lt dl gt   lt dt gt Primes under 100 lt  dt gt   lt dd gt  lt  dd gt   lt  dl gt  x000D   x000D   x000D

User · Answer

Here are the Brute-force iterative method and Sieve of Eratosthenes method to find prime numbers upto n  The performance of the second method is better than first in terms of time complexity  Brute-force iterative  function findPrime n      var res    2         isNotPrime     for  var i   3  i  lt  n  i          isNotPrime   res some checkDivisorExist       if    isNotPrime           res push i                function checkDivisorExist  j        return i   j     0         return res      Sieve of Eratosthenes method  function seiveOfErasthones  n      var listOfNum  range n         i   2        CHeck only until the square of the prime is less than number   while  i i  lt  n  amp  amp  i  lt  n        listOfNum   filterMultiples listOfNum  i       i           return listOfNum      function range  num        var res           for  var i   2  i  lt   num  i            res push i             return res         function filterMultiples  list  x        return list filter function  item             Include numbers smaller than x as they are already prime       return  item  lt   x      item  gt  x  amp  amp  item   x     0

User · Answer

I have created a JSFiddle showing how it should work in a readable way    idea is to have two functions isPrime and getPrimeNumbers to separate functionality  as well as using Math pow and initial value of 2  as it should be always there  see the jsfiddle attached jsFiddle  window onload   function        function         var cont   document getElementById  MainContainer        var curEl   document createElement  span        var primeNumbers    2        function fillContent             var primeNumbersContent   document createTextNode JSON stringify primeNumbers            curEl appendChild primeNumbersContent           cont appendChild curEl              function isPrime n            var divisor   2          while  n  gt  divisor                if  Math pow divisor  2   gt  n                    return true                            if  n   divisor    0    Math sqrt divisor   gt  n                    return false                else                   divisor                                    return true             function getPrimeNumbers range            for  var i   3  i  lt   range  i  2                if  isPrime i                     primeNumbers push i                                   fillContent primeNumbers             getPrimeNumbers 11

User · Answer

To find prime numbers between 0 to n  You just have to check if a number x is getting divisible by any number between 0 -  square root of x   If we pass n and to find all prime numbers between 0 and n   logic can be implemented as -      function findPrimeNums n                var x  3 j i 2         primeArr  2  isPrime         for   x lt  n x  2              j    int  Math sqrt  x              isPrime   true             for  i   2  i  lt   j  i                                 if  x   i    0                       isPrime   false                      break                                              if isPrime                   primeArr push x                                        return primeArr

User · Answer

I was searching how to find out prime number and went through above code which are too long  I found out a new easy solution for prime number and add them using filter  Kindly suggest me if there is any mistake in my code as I am a beginner  function sumPrimes num     let newNum        for let i   2  i  lt   num  i      newNum push i    for let i in newNum     newNum   newNum filter item   gt  item    newNum i     item   newNum i      0     return newNum reduce  a b    gt  a b     sumPrimes 10

User · Answer

I recently came up with a one-line solution that accomplishes exactly this for a JS challenge on Scrimba  below   ES6  const getPrimes num  gt Array num-1  fill   map  e i   gt 2 i  filter  e i a   gt a slice 0 i  every x  gt e x   0      lt  ES6 function getPrimes num  return  quot   quot  repeat num  slice 0 -1  split      map function e i  return i 1   filter function e  return e gt 1   filter function x  return  quot   quot  repeat x  slice 0 -1  split      map function f j  return j   filter function e  return e gt 1   every function e  return x e   0        This is the logic explained   First  the function builds an array of all numbers leading up to the desired number  in this case  100  via the  repeat   function using the desired number  100  as the repeater argument and then mapping the array to the indexes 1 to get the range of numbers from 0 to that number  0-100   A bit of string splitting and joining magic going on here  I m happy to explain this step further if you like   We exclude 0 and 1 from the array as they should not be tested for prime  lest they give a false positive  Neither are prime  We do this using  filter   for only numbers  gt  1    2    Now  we filter our new array of all integers between 2 and the desired number  100  for only prime numbers  To filter for prime numbers only  we use some of the same magic from our first step  We use  filter   and  repeat   once again to create a new array from 2 to each value from our new array of numbers  For each value s new array  we check to see if any of the numbers   2 and  lt  that number are factors of the number  We can do this using the  every   method paired with the modulo operator   to check if that number has any remainders when divided by any of those values between 2 and itself  If each value has remainders  x e   0   the condition is met for all values from 2 to that number  but not including that number  i e    2 99   and we can say that number is prime  The filter functions returns all prime numbers to the uppermost return  thereby returning the list of prime values between 2 and the passed value    As an example  using one of these functions I ve added above  returns the following  getPrimes 100        gt   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

User · Answer

A version without any loop  Use this against any array you have  ie    1 2 3   100  filter x  gt isPrime x    const isPrime   n   gt    if n   1   return false    if  2 3 5 7  includes n    return true    return n 2  0  amp  amp  n 3  0  amp  amp  n 5  0  amp  amp  n 7  0

User · Answer

I modified Rinto s answer just for those who don t want to use the prompt method and just want to see the program print prime numbers   its working   for  n   0  n  lt  100  n          var x   1      if  n    0    n    1  x   0      for  i   2  i  lt  n  i              if  n   i    0                x   0              break                      if  x    1               if prime print the numbers          document write n         else              if not prime print the number do nothing

User · Answer

And this famous code from a famous JS Ninja  var isPrime   n   gt  Array Math ceil Math sqrt n  1   fill   map  e i   gt i  slice 2  every m   gt  n m    console log Array 100  fill   map  e i   gt i 1  slice 1  filter isPrime

User · Answer

You can use this for any size of array of prime numbers  Hope this helps   x000D   x000D   function prime     x000D     var num   2  x000D   x000D     var body   document getElementById  solution    x000D   x000D     var len   arguments length  x000D     var flag   true  x000D   x000D     for  j   0  j  lt  len  j      x000D   x000D       for  i   num  i  lt  arguments j   i      x000D   x000D         if  arguments j    i    0    x000D           body innerHTML    arguments j      False  lt br   gt    x000D           flag   false  x000D           break  x000D   x000D           else   x000D           flag   true  x000D   x000D           x000D   x000D         x000D       if  flag    x000D         body innerHTML    arguments j      True  lt br   gt    x000D   x000D         x000D   x000D       x000D   x000D     x000D   x000D   var data    1  2  3  4  5  6  7  8  9  10   x000D   x000D   prime apply null  data   x000D   lt div id  solution  gt  x000D   x000D   lt  div gt  x000D   x000D   x000D

User · Answer

Here is a way to test if number is prime number    function isPrime numb     if  numb   2    0  return false    for  var i 3  i lt   Math sqrt numb   i   i   2        if  numb   i    0         return false              return true

User · Answer

How about something like this   next prime  for  var i   2  i  lt  100  i         for  var e   2  e  lt  i  e             if  i   e     0  continue next prime            console log i     lt br gt

User · Answer

Using recursion combined with the square root rule from here  checks whether a number is prime or not   function isPrime num           An integer is prime if it is not divisible by any prime less than or equal to its square root     var squareRoot   parseInt Math sqrt num        var primeCountUp   function divisor           if divisor  gt  squareRoot                   got to a point where the divisor is greater than                 the square root  therefore it is prime             return true                    else if num   divisor     0                   found a result that divides evenly  NOT prime             return false                    else                  keep counting             return primeCountUp   divisor                            start   2 because everything is divisible by 1     return primeCountUp 2

User · Answer

Here is my solution using Sieve of Eratosthenes method   function gimmePrimes num      numArray            first generate array of numbers  2 3    num    for  i   2  i  lt   num    i        numArray push i          for  i   0  i  lt  numArray length    i          this for loop helps to go through each element of array      for  j   numArray i   j  lt  numArray numArray length - 1     j            get s the value of i th element       for  k   2  j   k  lt   numArray numArray length - 1     k              find the index of multiples of ith element in the array         index   numArray indexOf j   k           if  index  gt  -1      remove the multiples           numArray splice index  1                                  return numArray    return result   gimmePrimes 100

User · Answer

First  change your inner code for another loop  for and while  so you can repeat the same code for different values   More specific for your problem  if you want to know if a given n is prime  you need to divide it for all values between 2 and sqrt n   If any of the modules is 0  it is not prime   If you want to find all primes  you can speed it and check n only by dividing by the previously found primes  Another way of speeding the process is the fact that  apart from 2 and 3  all the primes are 6 k plus or less 1

User · Answer

Here s the very simple way to calculate primes between a given range 1 to limit    Simple Solution       public static void getAllPrimeNumbers int limit             System out println  Printing prime number from 1 to     limit            for int number 2  number lt  limit  number                      print all prime numbers upto limit                if isPrime number                    System out println number                                       public static boolean isPrime int num            if  num    0    num    1                return false                    if  num    2                 return true                     for  int i   2  i  lt   num   2  i                  if  num   i    0                    return false                                  return true

User · Answer

A list built using the new features of ES6  especially with generator  Go to https   codepen io arius pen wqmzGp made in Catalan language for classes with my students  I hope you find it useful    x000D   x000D  function  Primer max     x000D    const infinite    max  amp  amp  max     0  x000D    const re                 1      x000D    let current   1  x000D    x000D    while  infinite    max--     x000D        if  re test  1  repeat current      true  yield current  x000D        current   x000D       x000D     x000D   x000D   x000D  let     list    Primer 100    x000D  console log list   x000D   x000D   x000D

User · Answer

I have slightly modified the Sieve of Sundaram algorithm to cut the unnecessary iterations and it seems to be very fast   This algorithm is actually two times faster than the most accepted  Ted Hopp s solution under this topic  Solving the 78498 primes between 0 - 1M takes like 20 25 msec in Chrome 55 and  lt  90 msec in FF 50 1  Also  vitaly-t s get next prime algorithm looks interesting but also results much slower   This is the core algorithm  One could apply segmentation and threading to get superb results    x000D   x000D   use strict   x000D  function primeSieve n   x000D    var a   Array n   n 2   x000D        t    Math sqrt 4 8 n -2  4  x000D        u   0  x000D        r       x000D    for var i   1  i  lt   t  i     x000D      u    n-i   1 2 i   x000D      for var j   i  j  lt   u  j    a i   j   2 i j    true  x000D      x000D    for var i   0  i lt   n  i     a i   amp  amp  r push i 2 1   x000D    return r  x000D    x000D   x000D  var primes       x000D  console time  primes    x000D  primes   primeSieve 1000000   x000D  console timeEnd  primes    x000D  console log primes length   x000D   x000D   x000D    The loop limits explained   Just like the Sieve of Erasthotenes  the Sieve of Sundaram algorithm also crosses out some selected integers from the list  To select which integers to cross out the rule is i   j   2ij   n where i and j are two indices and n is the number of the total elements  Once we cross out every i   j   2ij  the remaining numbers are doubled and oddified  2n 1  to reveal a list of prime numbers  The final stage is in fact the auto discounting of the even numbers  It s proof is beautifully explained here   Sieve of Sundaram is only fast if the loop indices start and end limits are correctly selected such that there shall be no  or minimal  redundant  multiple  elimination of the non-primes  As we need i and j values to calculate the numbers to cross out  i   j   2ij up to n let s see how we can approach   i  So we have to find the the max value i and j can take when they are equal  Which is 2i   2i 2   n  We can easily solve the positive value for i by using the quadratic formula and that is the line with t    Math sqrt 4 8 n -2  4   j  The inner loop index j should start from i and run up to the point it can go with the current i value  No more than that  Since we know that i   j   2ij   n  this can easily be calculated as u    n-i   1 2 i    While this will not completely remove the redundant crossings it will  greatly  eliminate the redundancy  For instance for n   50  to check for primes up to 100  instead of doing 50 x 50   2500  we will do only 30 iterations in total  So clearly  this algorithm shouldn t be considered as an O n 2  time complexity one   i  j  v 1  1  4 1  2  7 1  3 10 1  4 13 1  5 16 1  6 19 1  7 22   lt  lt  1  8 25 1  9 28 1 10 31   lt  lt  1 11 34 1 12 37   lt  lt  1 13 40   lt  lt  1 14 43 1 15 46 1 16 49   lt  lt  2  2 12 2  3 17 2  4 22   lt  lt  dupe  1 2  5 27 2  6 32 2  7 37   lt  lt  dupe  2 2  8 42 2  9 47 3  3 24 3  4 31   lt  lt  dupe  3 3  5 38 3  6 45 4  4 40   lt  lt  dupe  4 4  5 49   lt  lt  dupe  5   among which there are only 5 duplicates  22  31  37  40  49  The redundancy is around 20  for n   100 however it increases to  300  for n   10M  Which means a further optimization of SoS bears the potentital to obtain the results even faster as n grows  So one idea might be segmentation and to keep n small all the time   So OK   I have decided to take this quest a little further   After some careful examination of the repeated crossings I have come to the awareness of the fact that  by the exception of i     1 case  if either one or both of the i or j index value is among 4 7 10 13 16 19    series  a duplicate crossing is generated  Then allowing the inner loop to turn only when i 3-1     0  a further cut down like 35-40  from the total number of the loops is achieved  So for instance for 1M integers the nested loop s total turn count dropped to like 1M from 1 4M  Wow    We are talking almost O n  here   I have just made a test  In JS  just an empty loop counting up to 1B takes like 4000ms  In the below modified algorithm  finding the primes up to 100M takes the same amount of time   I have also implemented the segmentation part of this algorithm to push to the workers  So that we will be able to use multiple threads too  But that code will follow a little later   So let me introduce you the modified Sieve of Sundaram probably at it s best when not segmented  It shall compute the primes between 0-1M in about 15-20ms with Chrome V8 and Edge ChakraCore    x000D   x000D   use strict   x000D  function primeSieve n   x000D    var a   Array n   n 2   x000D        t    Math sqrt 4 8 n -2  4  x000D        u   0  x000D        r       x000D    for var i   1  i  lt   n-1  3  i    a 1 3 i    true  x000D    for var i   2  i  lt   t  i     x000D      u    n-i   1 2 i   x000D      if  i 3-1  for var j   i  j  lt  u  j    a i   j   2 i j    true  x000D      x000D    for var i   0  i lt  n  i     a i   amp  amp  r push i 2 1   x000D    return r  x000D    x000D   x000D  var primes       x000D  console time  primes    x000D  primes   primeSieve 1000000   x000D  console timeEnd  primes    x000D  console log primes length   x000D   x000D   x000D    Well    finally I guess i have implemented a sieve  which is originated from the ingenious Sieve of Sundaram  such that it s the fastest JavaScript sieve that i could have found over the internet  including the  Odds only Sieve of Eratosthenes  or the  Sieve of Atkins   Also this is ready for the web workers  multi-threading   Think it this way  In this humble AMD PC for a single thread  it takes 3 300 ms for JS just to count up to 10 9 and the following optimized  segmented SoS  will get me the 50847534 primes up to 10 9 only in 14 000 ms  Which means 4 25 times the operation of just counting  I think it s impressive   You can test it for yourself    x000D   x000D  console time  tare    x000D  for  var i   0  i  lt  1000000000  i     x000D  console timeEnd  tare    x000D   x000D   x000D    And here i introduce you to the segmented Seieve of Sundaram at it s best    x000D   x000D   use strict   x000D  function findPrimes n   x000D     x000D    function primeSieve g o r   x000D      var t    Math sqrt 4 8  g o  -2  4  x000D          e   0  x000D          s   0  x000D       x000D      ar fill true   x000D      if  o    x000D        for var i   Math ceil  o-1  3   i  lt   g o-1  3  i    ar 1 3 i-o    false  x000D        for var i   2  i  lt  t  i     x000D          s   Math ceil  o-i   1 2 i    x000D          e    g o-i   1 2 i   x000D          if  i 3-1  for var j   s  j  lt  e  j    ar i   j   2 i j-o    false  x000D          x000D        else   x000D          for var i   1  i  lt   g-1  3  i    ar 1 3 i    false  x000D          for var i   2  i  lt  t  i     x000D            e    g-i   1 2 i   x000D            if  i 3-1  for var j   i  j  lt  e  j    ar i   j   2 i j    false  x000D            x000D          x000D      for var i   0  i  lt  g  i    ar i   amp  amp  r push  i o  2 1   x000D      return r  x000D      x000D     x000D    var cs   n  lt   1e6   7500 x000D                        n  lt   1e7   60000 x000D                                   100000     chunk size x000D        cc      n cs                          chunk count x000D        xs   n   cs                           excess after last chunk x000D        ar   Array cs 2                       array used as map x000D    result       x000D     x000D    for var i   0  i  lt  cc  i    result   primeSieve cs 2 i cs 2 result   x000D    result   xs   primeSieve xs 2 cc cs 2 result    result  x000D    result 0    2  x000D    return result  x000D    x000D   x000D   x000D  var primes       x000D  console time  primes    x000D  primes   findPrimes 1000000000   x000D  console timeEnd  primes    x000D  console log primes length   x000D   x000D   x000D    I am not sure if it gets any better than this  I would love to hear your opinions

User · Answer

lt code gt   lt script language  javascript  gt     var n prompt  Enter User Value        var x 1         if n  0    n  1  x 0            for i 2 i lt n i                           if n i  0                x 0       break                                   if x  1                                 alert n        is prime                                else                                alert n        is not prime                                lt  script gt

User · Answer

Luchian s answer gives you a link to the standard technique for finding primes   A less efficient  but simpler approach is to turn your existing code into a nested loop   Observe that you are dividing by 2 3 4 5 6 and so on     and turn that into a loop   Given that this is homework  and given that the aim of the homework is to help you learn basic programming  a solution that is simple  correct but somewhat inefficient should be fine

[javascript] How to find prime numbers between 0 - 100?

Examples related to javascript

Examples related to math

Examples related to primes