Fastest prime generating algorithm












16












$begingroup$


What is the fastest known algorithm that generates all distinct prime numbers less than n?



Is it faster than Sieve of Atkin?










share|cite|improve this question











$endgroup$












  • $begingroup$
    You can't generate all prime numbers nor an infinite subset of all prime numbers in finite time...
    $endgroup$
    – FUZxxl
    Sep 29 '11 at 9:02






  • 4




    $begingroup$
    Ok, time to reopen
    $endgroup$
    – grok_it
    Sep 29 '11 at 13:09










  • $begingroup$
    Sieve of Eratosthenes for reference takes O(n)+P(n)(n/k) time and P(n)log(n)+k space. Iteratively apply the sieve to the next k numbers; for each prime keep track of the smallest prime multiple you have seen.
    $endgroup$
    – Chad Brewbaker
    Nov 16 '12 at 16:27
















16












$begingroup$


What is the fastest known algorithm that generates all distinct prime numbers less than n?



Is it faster than Sieve of Atkin?










share|cite|improve this question











$endgroup$












  • $begingroup$
    You can't generate all prime numbers nor an infinite subset of all prime numbers in finite time...
    $endgroup$
    – FUZxxl
    Sep 29 '11 at 9:02






  • 4




    $begingroup$
    Ok, time to reopen
    $endgroup$
    – grok_it
    Sep 29 '11 at 13:09










  • $begingroup$
    Sieve of Eratosthenes for reference takes O(n)+P(n)(n/k) time and P(n)log(n)+k space. Iteratively apply the sieve to the next k numbers; for each prime keep track of the smallest prime multiple you have seen.
    $endgroup$
    – Chad Brewbaker
    Nov 16 '12 at 16:27














16












16








16


4



$begingroup$


What is the fastest known algorithm that generates all distinct prime numbers less than n?



Is it faster than Sieve of Atkin?










share|cite|improve this question











$endgroup$




What is the fastest known algorithm that generates all distinct prime numbers less than n?



Is it faster than Sieve of Atkin?







algorithms prime-numbers






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 16 '12 at 17:32









Martin Argerami

128k1184184




128k1184184










asked Sep 29 '11 at 8:58









grok_itgrok_it

2621210




2621210












  • $begingroup$
    You can't generate all prime numbers nor an infinite subset of all prime numbers in finite time...
    $endgroup$
    – FUZxxl
    Sep 29 '11 at 9:02






  • 4




    $begingroup$
    Ok, time to reopen
    $endgroup$
    – grok_it
    Sep 29 '11 at 13:09










  • $begingroup$
    Sieve of Eratosthenes for reference takes O(n)+P(n)(n/k) time and P(n)log(n)+k space. Iteratively apply the sieve to the next k numbers; for each prime keep track of the smallest prime multiple you have seen.
    $endgroup$
    – Chad Brewbaker
    Nov 16 '12 at 16:27


















  • $begingroup$
    You can't generate all prime numbers nor an infinite subset of all prime numbers in finite time...
    $endgroup$
    – FUZxxl
    Sep 29 '11 at 9:02






  • 4




    $begingroup$
    Ok, time to reopen
    $endgroup$
    – grok_it
    Sep 29 '11 at 13:09










  • $begingroup$
    Sieve of Eratosthenes for reference takes O(n)+P(n)(n/k) time and P(n)log(n)+k space. Iteratively apply the sieve to the next k numbers; for each prime keep track of the smallest prime multiple you have seen.
    $endgroup$
    – Chad Brewbaker
    Nov 16 '12 at 16:27
















$begingroup$
You can't generate all prime numbers nor an infinite subset of all prime numbers in finite time...
$endgroup$
– FUZxxl
Sep 29 '11 at 9:02




$begingroup$
You can't generate all prime numbers nor an infinite subset of all prime numbers in finite time...
$endgroup$
– FUZxxl
Sep 29 '11 at 9:02




4




4




$begingroup$
Ok, time to reopen
$endgroup$
– grok_it
Sep 29 '11 at 13:09




$begingroup$
Ok, time to reopen
$endgroup$
– grok_it
Sep 29 '11 at 13:09












$begingroup$
Sieve of Eratosthenes for reference takes O(n)+P(n)(n/k) time and P(n)log(n)+k space. Iteratively apply the sieve to the next k numbers; for each prime keep track of the smallest prime multiple you have seen.
$endgroup$
– Chad Brewbaker
Nov 16 '12 at 16:27




$begingroup$
Sieve of Eratosthenes for reference takes O(n)+P(n)(n/k) time and P(n)log(n)+k space. Iteratively apply the sieve to the next k numbers; for each prime keep track of the smallest prime multiple you have seen.
$endgroup$
– Chad Brewbaker
Nov 16 '12 at 16:27










4 Answers
4






active

oldest

votes


















11












$begingroup$


What is the fastest known algorithm that generates all prime numbers?




I assume you mean: Given $n$, what is the fastest known algorithm that generates all prime numbers $p le n$ ? Currently it is the Sieve of Atkin.




And what is the fastest known algorithm that generates any infinite subset of the prime numbers?




Again, I assume you mean: Given $n$, how fast can I generate $n$ distinct primes? There might be a faster method than the Sieve of Atkin, but I don't know of any. A good question!




And is there a theoretical lowest possible O(n) of such programs?




Is $n$ the number of primes you want to generate? Then it would take $O(n)$ operations just to store them in memory. So yes. But if you want to generate all primes $p le n$ , the Sieve of Atkin has time complexity $O(n/log log n)$ . So no.






share|cite|improve this answer









$endgroup$









  • 7




    $begingroup$
    @Robert: So? The question was about: asymptotic time complexity. The OP specifically used the notation O(n).
    $endgroup$
    – TonyK
    Sep 29 '11 at 11:26






  • 1




    $begingroup$
    In practice, the Atkin-Bernstein sieve isn't the fastest at any range. Sieve of Eratosthenes variants outperform it at all sizes.
    $endgroup$
    – Charles
    Sep 29 '11 at 13:19






  • 1




    $begingroup$
    @Charles: the paper at cr.yp.to/papers/primesieves-19990826.pdf suggests otherwise - Atkin-Bernstein outperformed Eratosthenes by 15.0 seconds to 19.6 seconds in generating all primes up to $1000000000$ . The fact that the benchmark programs were written by one of the creators (Bernstein) of the Aktin Sieve means that we have to be cautious in interpreting them; but knowing Bernstein's work, and given that higher numbers are now reachable (the paper was written in 1999), I think you must be wrong.
    $endgroup$
    – TonyK
    Sep 29 '11 at 13:31








  • 1




    $begingroup$
    @TonyK: I have only the highest respect for Dr. Bernstein--he does great theoretical work that is very practically accessible. But if you download yafu and primegen right now I think you'll see that yafu outperforms slightly for 32-bit limits and greatly outperforms above that point.
    $endgroup$
    – Charles
    Sep 29 '11 at 13:34






  • 3




    $begingroup$
    In base ten we know anything with more than one digit ending in 0,2,4,5,6,8 is nonprime. For tractable $n$ why not just use base 2*3*5*7*11*13*17*19...k? You can then make a suffix list of known nonprimes in the base up to k which you avoid, and from this you throw it against a sieve that includes everything you have found. Every so often you rebase. Ideally you want to use only P(n)*log(n) space. Atkin takes O(n) memory too...
    $endgroup$
    – Chad Brewbaker
    Nov 16 '12 at 16:03



















1












$begingroup$

I recently just chanced upon a particular logic. All prime numbers either fall in multiples of 6n+1 or 6n-1 except for 2 and 3.



Using this the search space could be considerably reduced for applying any sieve such as Atkins or Eratosthenes. Hence making it a slightly better form of finding primes.






share|cite|improve this answer









$endgroup$









  • 2




    $begingroup$
    This is en.wikipedia.org/wiki/Wheel_factorization for n=2*3.
    $endgroup$
    – Iiridayn
    Nov 29 '14 at 19:12










  • $begingroup$
    @sohaib, in essence it is enough to consider 2/6 = 1/3 of N to get all the primes below N (since we need to consider only the two progressions (6k+1) and (6k-1) and add 2 at the end to account for primes 2 and 3. One can even write pi(n)+c(n)=N/3. Here, c(n) is the number of composite within the two progressions. And there is an easy way to get those if you work with indices instead of numbers.
    $endgroup$
    – user25406
    Dec 18 '16 at 12:18



















0












$begingroup$

The sieve of Eratosthenes is one of the most efficient ways to find all the prime number less than n.



Implemenation of Algorithm






share|cite|improve this answer









$endgroup$





















    -1












    $begingroup$

    Odd numbers can be wheeled in multiplications to output only odd composite numbers. Then the odd numbers that are not output are the prime numbers.



    Now each inner loop can stop at a multiplication that reaches the value of an upper-bound and the outer loop can stop at the square root of the upper-bound.



    Furthermore the loops from the number 11 can increment with 2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10 ... as continuting and repeating. That's a big performance gain because multiples of 3, 5, and 7 are removed from the sequence of odd numbers.



    A prime number application really works best when outputting prime numbers between an upper bound and the upper bound - n. Then the application appears to be just scrolling sections (or jumping to sections) of a list on each computation. And in this case the loop increments are really only needed on the outer loop because a single division operation jumps over unneeded sections of the inner loop. Of course, array subscript locations can work with translations such that the same array can handle any of the segmented computations and then not use very much memory.






    share|cite|improve this answer











    $endgroup$












      protected by dxiv Dec 22 '17 at 6:46



      Thank you for your interest in this question.
      Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).



      Would you like to answer one of these unanswered questions instead?














      4 Answers
      4






      active

      oldest

      votes








      4 Answers
      4






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      11












      $begingroup$


      What is the fastest known algorithm that generates all prime numbers?




      I assume you mean: Given $n$, what is the fastest known algorithm that generates all prime numbers $p le n$ ? Currently it is the Sieve of Atkin.




      And what is the fastest known algorithm that generates any infinite subset of the prime numbers?




      Again, I assume you mean: Given $n$, how fast can I generate $n$ distinct primes? There might be a faster method than the Sieve of Atkin, but I don't know of any. A good question!




      And is there a theoretical lowest possible O(n) of such programs?




      Is $n$ the number of primes you want to generate? Then it would take $O(n)$ operations just to store them in memory. So yes. But if you want to generate all primes $p le n$ , the Sieve of Atkin has time complexity $O(n/log log n)$ . So no.






      share|cite|improve this answer









      $endgroup$









      • 7




        $begingroup$
        @Robert: So? The question was about: asymptotic time complexity. The OP specifically used the notation O(n).
        $endgroup$
        – TonyK
        Sep 29 '11 at 11:26






      • 1




        $begingroup$
        In practice, the Atkin-Bernstein sieve isn't the fastest at any range. Sieve of Eratosthenes variants outperform it at all sizes.
        $endgroup$
        – Charles
        Sep 29 '11 at 13:19






      • 1




        $begingroup$
        @Charles: the paper at cr.yp.to/papers/primesieves-19990826.pdf suggests otherwise - Atkin-Bernstein outperformed Eratosthenes by 15.0 seconds to 19.6 seconds in generating all primes up to $1000000000$ . The fact that the benchmark programs were written by one of the creators (Bernstein) of the Aktin Sieve means that we have to be cautious in interpreting them; but knowing Bernstein's work, and given that higher numbers are now reachable (the paper was written in 1999), I think you must be wrong.
        $endgroup$
        – TonyK
        Sep 29 '11 at 13:31








      • 1




        $begingroup$
        @TonyK: I have only the highest respect for Dr. Bernstein--he does great theoretical work that is very practically accessible. But if you download yafu and primegen right now I think you'll see that yafu outperforms slightly for 32-bit limits and greatly outperforms above that point.
        $endgroup$
        – Charles
        Sep 29 '11 at 13:34






      • 3




        $begingroup$
        In base ten we know anything with more than one digit ending in 0,2,4,5,6,8 is nonprime. For tractable $n$ why not just use base 2*3*5*7*11*13*17*19...k? You can then make a suffix list of known nonprimes in the base up to k which you avoid, and from this you throw it against a sieve that includes everything you have found. Every so often you rebase. Ideally you want to use only P(n)*log(n) space. Atkin takes O(n) memory too...
        $endgroup$
        – Chad Brewbaker
        Nov 16 '12 at 16:03
















      11












      $begingroup$


      What is the fastest known algorithm that generates all prime numbers?




      I assume you mean: Given $n$, what is the fastest known algorithm that generates all prime numbers $p le n$ ? Currently it is the Sieve of Atkin.




      And what is the fastest known algorithm that generates any infinite subset of the prime numbers?




      Again, I assume you mean: Given $n$, how fast can I generate $n$ distinct primes? There might be a faster method than the Sieve of Atkin, but I don't know of any. A good question!




      And is there a theoretical lowest possible O(n) of such programs?




      Is $n$ the number of primes you want to generate? Then it would take $O(n)$ operations just to store them in memory. So yes. But if you want to generate all primes $p le n$ , the Sieve of Atkin has time complexity $O(n/log log n)$ . So no.






      share|cite|improve this answer









      $endgroup$









      • 7




        $begingroup$
        @Robert: So? The question was about: asymptotic time complexity. The OP specifically used the notation O(n).
        $endgroup$
        – TonyK
        Sep 29 '11 at 11:26






      • 1




        $begingroup$
        In practice, the Atkin-Bernstein sieve isn't the fastest at any range. Sieve of Eratosthenes variants outperform it at all sizes.
        $endgroup$
        – Charles
        Sep 29 '11 at 13:19






      • 1




        $begingroup$
        @Charles: the paper at cr.yp.to/papers/primesieves-19990826.pdf suggests otherwise - Atkin-Bernstein outperformed Eratosthenes by 15.0 seconds to 19.6 seconds in generating all primes up to $1000000000$ . The fact that the benchmark programs were written by one of the creators (Bernstein) of the Aktin Sieve means that we have to be cautious in interpreting them; but knowing Bernstein's work, and given that higher numbers are now reachable (the paper was written in 1999), I think you must be wrong.
        $endgroup$
        – TonyK
        Sep 29 '11 at 13:31








      • 1




        $begingroup$
        @TonyK: I have only the highest respect for Dr. Bernstein--he does great theoretical work that is very practically accessible. But if you download yafu and primegen right now I think you'll see that yafu outperforms slightly for 32-bit limits and greatly outperforms above that point.
        $endgroup$
        – Charles
        Sep 29 '11 at 13:34






      • 3




        $begingroup$
        In base ten we know anything with more than one digit ending in 0,2,4,5,6,8 is nonprime. For tractable $n$ why not just use base 2*3*5*7*11*13*17*19...k? You can then make a suffix list of known nonprimes in the base up to k which you avoid, and from this you throw it against a sieve that includes everything you have found. Every so often you rebase. Ideally you want to use only P(n)*log(n) space. Atkin takes O(n) memory too...
        $endgroup$
        – Chad Brewbaker
        Nov 16 '12 at 16:03














      11












      11








      11





      $begingroup$


      What is the fastest known algorithm that generates all prime numbers?




      I assume you mean: Given $n$, what is the fastest known algorithm that generates all prime numbers $p le n$ ? Currently it is the Sieve of Atkin.




      And what is the fastest known algorithm that generates any infinite subset of the prime numbers?




      Again, I assume you mean: Given $n$, how fast can I generate $n$ distinct primes? There might be a faster method than the Sieve of Atkin, but I don't know of any. A good question!




      And is there a theoretical lowest possible O(n) of such programs?




      Is $n$ the number of primes you want to generate? Then it would take $O(n)$ operations just to store them in memory. So yes. But if you want to generate all primes $p le n$ , the Sieve of Atkin has time complexity $O(n/log log n)$ . So no.






      share|cite|improve this answer









      $endgroup$




      What is the fastest known algorithm that generates all prime numbers?




      I assume you mean: Given $n$, what is the fastest known algorithm that generates all prime numbers $p le n$ ? Currently it is the Sieve of Atkin.




      And what is the fastest known algorithm that generates any infinite subset of the prime numbers?




      Again, I assume you mean: Given $n$, how fast can I generate $n$ distinct primes? There might be a faster method than the Sieve of Atkin, but I don't know of any. A good question!




      And is there a theoretical lowest possible O(n) of such programs?




      Is $n$ the number of primes you want to generate? Then it would take $O(n)$ operations just to store them in memory. So yes. But if you want to generate all primes $p le n$ , the Sieve of Atkin has time complexity $O(n/log log n)$ . So no.







      share|cite|improve this answer












      share|cite|improve this answer



      share|cite|improve this answer










      answered Sep 29 '11 at 9:30









      TonyKTonyK

      43k356135




      43k356135








      • 7




        $begingroup$
        @Robert: So? The question was about: asymptotic time complexity. The OP specifically used the notation O(n).
        $endgroup$
        – TonyK
        Sep 29 '11 at 11:26






      • 1




        $begingroup$
        In practice, the Atkin-Bernstein sieve isn't the fastest at any range. Sieve of Eratosthenes variants outperform it at all sizes.
        $endgroup$
        – Charles
        Sep 29 '11 at 13:19






      • 1




        $begingroup$
        @Charles: the paper at cr.yp.to/papers/primesieves-19990826.pdf suggests otherwise - Atkin-Bernstein outperformed Eratosthenes by 15.0 seconds to 19.6 seconds in generating all primes up to $1000000000$ . The fact that the benchmark programs were written by one of the creators (Bernstein) of the Aktin Sieve means that we have to be cautious in interpreting them; but knowing Bernstein's work, and given that higher numbers are now reachable (the paper was written in 1999), I think you must be wrong.
        $endgroup$
        – TonyK
        Sep 29 '11 at 13:31








      • 1




        $begingroup$
        @TonyK: I have only the highest respect for Dr. Bernstein--he does great theoretical work that is very practically accessible. But if you download yafu and primegen right now I think you'll see that yafu outperforms slightly for 32-bit limits and greatly outperforms above that point.
        $endgroup$
        – Charles
        Sep 29 '11 at 13:34






      • 3




        $begingroup$
        In base ten we know anything with more than one digit ending in 0,2,4,5,6,8 is nonprime. For tractable $n$ why not just use base 2*3*5*7*11*13*17*19...k? You can then make a suffix list of known nonprimes in the base up to k which you avoid, and from this you throw it against a sieve that includes everything you have found. Every so often you rebase. Ideally you want to use only P(n)*log(n) space. Atkin takes O(n) memory too...
        $endgroup$
        – Chad Brewbaker
        Nov 16 '12 at 16:03














      • 7




        $begingroup$
        @Robert: So? The question was about: asymptotic time complexity. The OP specifically used the notation O(n).
        $endgroup$
        – TonyK
        Sep 29 '11 at 11:26






      • 1




        $begingroup$
        In practice, the Atkin-Bernstein sieve isn't the fastest at any range. Sieve of Eratosthenes variants outperform it at all sizes.
        $endgroup$
        – Charles
        Sep 29 '11 at 13:19






      • 1




        $begingroup$
        @Charles: the paper at cr.yp.to/papers/primesieves-19990826.pdf suggests otherwise - Atkin-Bernstein outperformed Eratosthenes by 15.0 seconds to 19.6 seconds in generating all primes up to $1000000000$ . The fact that the benchmark programs were written by one of the creators (Bernstein) of the Aktin Sieve means that we have to be cautious in interpreting them; but knowing Bernstein's work, and given that higher numbers are now reachable (the paper was written in 1999), I think you must be wrong.
        $endgroup$
        – TonyK
        Sep 29 '11 at 13:31








      • 1




        $begingroup$
        @TonyK: I have only the highest respect for Dr. Bernstein--he does great theoretical work that is very practically accessible. But if you download yafu and primegen right now I think you'll see that yafu outperforms slightly for 32-bit limits and greatly outperforms above that point.
        $endgroup$
        – Charles
        Sep 29 '11 at 13:34






      • 3




        $begingroup$
        In base ten we know anything with more than one digit ending in 0,2,4,5,6,8 is nonprime. For tractable $n$ why not just use base 2*3*5*7*11*13*17*19...k? You can then make a suffix list of known nonprimes in the base up to k which you avoid, and from this you throw it against a sieve that includes everything you have found. Every so often you rebase. Ideally you want to use only P(n)*log(n) space. Atkin takes O(n) memory too...
        $endgroup$
        – Chad Brewbaker
        Nov 16 '12 at 16:03








      7




      7




      $begingroup$
      @Robert: So? The question was about: asymptotic time complexity. The OP specifically used the notation O(n).
      $endgroup$
      – TonyK
      Sep 29 '11 at 11:26




      $begingroup$
      @Robert: So? The question was about: asymptotic time complexity. The OP specifically used the notation O(n).
      $endgroup$
      – TonyK
      Sep 29 '11 at 11:26




      1




      1




      $begingroup$
      In practice, the Atkin-Bernstein sieve isn't the fastest at any range. Sieve of Eratosthenes variants outperform it at all sizes.
      $endgroup$
      – Charles
      Sep 29 '11 at 13:19




      $begingroup$
      In practice, the Atkin-Bernstein sieve isn't the fastest at any range. Sieve of Eratosthenes variants outperform it at all sizes.
      $endgroup$
      – Charles
      Sep 29 '11 at 13:19




      1




      1




      $begingroup$
      @Charles: the paper at cr.yp.to/papers/primesieves-19990826.pdf suggests otherwise - Atkin-Bernstein outperformed Eratosthenes by 15.0 seconds to 19.6 seconds in generating all primes up to $1000000000$ . The fact that the benchmark programs were written by one of the creators (Bernstein) of the Aktin Sieve means that we have to be cautious in interpreting them; but knowing Bernstein's work, and given that higher numbers are now reachable (the paper was written in 1999), I think you must be wrong.
      $endgroup$
      – TonyK
      Sep 29 '11 at 13:31






      $begingroup$
      @Charles: the paper at cr.yp.to/papers/primesieves-19990826.pdf suggests otherwise - Atkin-Bernstein outperformed Eratosthenes by 15.0 seconds to 19.6 seconds in generating all primes up to $1000000000$ . The fact that the benchmark programs were written by one of the creators (Bernstein) of the Aktin Sieve means that we have to be cautious in interpreting them; but knowing Bernstein's work, and given that higher numbers are now reachable (the paper was written in 1999), I think you must be wrong.
      $endgroup$
      – TonyK
      Sep 29 '11 at 13:31






      1




      1




      $begingroup$
      @TonyK: I have only the highest respect for Dr. Bernstein--he does great theoretical work that is very practically accessible. But if you download yafu and primegen right now I think you'll see that yafu outperforms slightly for 32-bit limits and greatly outperforms above that point.
      $endgroup$
      – Charles
      Sep 29 '11 at 13:34




      $begingroup$
      @TonyK: I have only the highest respect for Dr. Bernstein--he does great theoretical work that is very practically accessible. But if you download yafu and primegen right now I think you'll see that yafu outperforms slightly for 32-bit limits and greatly outperforms above that point.
      $endgroup$
      – Charles
      Sep 29 '11 at 13:34




      3




      3




      $begingroup$
      In base ten we know anything with more than one digit ending in 0,2,4,5,6,8 is nonprime. For tractable $n$ why not just use base 2*3*5*7*11*13*17*19...k? You can then make a suffix list of known nonprimes in the base up to k which you avoid, and from this you throw it against a sieve that includes everything you have found. Every so often you rebase. Ideally you want to use only P(n)*log(n) space. Atkin takes O(n) memory too...
      $endgroup$
      – Chad Brewbaker
      Nov 16 '12 at 16:03




      $begingroup$
      In base ten we know anything with more than one digit ending in 0,2,4,5,6,8 is nonprime. For tractable $n$ why not just use base 2*3*5*7*11*13*17*19...k? You can then make a suffix list of known nonprimes in the base up to k which you avoid, and from this you throw it against a sieve that includes everything you have found. Every so often you rebase. Ideally you want to use only P(n)*log(n) space. Atkin takes O(n) memory too...
      $endgroup$
      – Chad Brewbaker
      Nov 16 '12 at 16:03











      1












      $begingroup$

      I recently just chanced upon a particular logic. All prime numbers either fall in multiples of 6n+1 or 6n-1 except for 2 and 3.



      Using this the search space could be considerably reduced for applying any sieve such as Atkins or Eratosthenes. Hence making it a slightly better form of finding primes.






      share|cite|improve this answer









      $endgroup$









      • 2




        $begingroup$
        This is en.wikipedia.org/wiki/Wheel_factorization for n=2*3.
        $endgroup$
        – Iiridayn
        Nov 29 '14 at 19:12










      • $begingroup$
        @sohaib, in essence it is enough to consider 2/6 = 1/3 of N to get all the primes below N (since we need to consider only the two progressions (6k+1) and (6k-1) and add 2 at the end to account for primes 2 and 3. One can even write pi(n)+c(n)=N/3. Here, c(n) is the number of composite within the two progressions. And there is an easy way to get those if you work with indices instead of numbers.
        $endgroup$
        – user25406
        Dec 18 '16 at 12:18
















      1












      $begingroup$

      I recently just chanced upon a particular logic. All prime numbers either fall in multiples of 6n+1 or 6n-1 except for 2 and 3.



      Using this the search space could be considerably reduced for applying any sieve such as Atkins or Eratosthenes. Hence making it a slightly better form of finding primes.






      share|cite|improve this answer









      $endgroup$









      • 2




        $begingroup$
        This is en.wikipedia.org/wiki/Wheel_factorization for n=2*3.
        $endgroup$
        – Iiridayn
        Nov 29 '14 at 19:12










      • $begingroup$
        @sohaib, in essence it is enough to consider 2/6 = 1/3 of N to get all the primes below N (since we need to consider only the two progressions (6k+1) and (6k-1) and add 2 at the end to account for primes 2 and 3. One can even write pi(n)+c(n)=N/3. Here, c(n) is the number of composite within the two progressions. And there is an easy way to get those if you work with indices instead of numbers.
        $endgroup$
        – user25406
        Dec 18 '16 at 12:18














      1












      1








      1





      $begingroup$

      I recently just chanced upon a particular logic. All prime numbers either fall in multiples of 6n+1 or 6n-1 except for 2 and 3.



      Using this the search space could be considerably reduced for applying any sieve such as Atkins or Eratosthenes. Hence making it a slightly better form of finding primes.






      share|cite|improve this answer









      $endgroup$



      I recently just chanced upon a particular logic. All prime numbers either fall in multiples of 6n+1 or 6n-1 except for 2 and 3.



      Using this the search space could be considerably reduced for applying any sieve such as Atkins or Eratosthenes. Hence making it a slightly better form of finding primes.







      share|cite|improve this answer












      share|cite|improve this answer



      share|cite|improve this answer










      answered Jan 23 '14 at 16:07









      Sohaib ISohaib I

      2611211




      2611211








      • 2




        $begingroup$
        This is en.wikipedia.org/wiki/Wheel_factorization for n=2*3.
        $endgroup$
        – Iiridayn
        Nov 29 '14 at 19:12










      • $begingroup$
        @sohaib, in essence it is enough to consider 2/6 = 1/3 of N to get all the primes below N (since we need to consider only the two progressions (6k+1) and (6k-1) and add 2 at the end to account for primes 2 and 3. One can even write pi(n)+c(n)=N/3. Here, c(n) is the number of composite within the two progressions. And there is an easy way to get those if you work with indices instead of numbers.
        $endgroup$
        – user25406
        Dec 18 '16 at 12:18














      • 2




        $begingroup$
        This is en.wikipedia.org/wiki/Wheel_factorization for n=2*3.
        $endgroup$
        – Iiridayn
        Nov 29 '14 at 19:12










      • $begingroup$
        @sohaib, in essence it is enough to consider 2/6 = 1/3 of N to get all the primes below N (since we need to consider only the two progressions (6k+1) and (6k-1) and add 2 at the end to account for primes 2 and 3. One can even write pi(n)+c(n)=N/3. Here, c(n) is the number of composite within the two progressions. And there is an easy way to get those if you work with indices instead of numbers.
        $endgroup$
        – user25406
        Dec 18 '16 at 12:18








      2




      2




      $begingroup$
      This is en.wikipedia.org/wiki/Wheel_factorization for n=2*3.
      $endgroup$
      – Iiridayn
      Nov 29 '14 at 19:12




      $begingroup$
      This is en.wikipedia.org/wiki/Wheel_factorization for n=2*3.
      $endgroup$
      – Iiridayn
      Nov 29 '14 at 19:12












      $begingroup$
      @sohaib, in essence it is enough to consider 2/6 = 1/3 of N to get all the primes below N (since we need to consider only the two progressions (6k+1) and (6k-1) and add 2 at the end to account for primes 2 and 3. One can even write pi(n)+c(n)=N/3. Here, c(n) is the number of composite within the two progressions. And there is an easy way to get those if you work with indices instead of numbers.
      $endgroup$
      – user25406
      Dec 18 '16 at 12:18




      $begingroup$
      @sohaib, in essence it is enough to consider 2/6 = 1/3 of N to get all the primes below N (since we need to consider only the two progressions (6k+1) and (6k-1) and add 2 at the end to account for primes 2 and 3. One can even write pi(n)+c(n)=N/3. Here, c(n) is the number of composite within the two progressions. And there is an easy way to get those if you work with indices instead of numbers.
      $endgroup$
      – user25406
      Dec 18 '16 at 12:18











      0












      $begingroup$

      The sieve of Eratosthenes is one of the most efficient ways to find all the prime number less than n.



      Implemenation of Algorithm






      share|cite|improve this answer









      $endgroup$


















        0












        $begingroup$

        The sieve of Eratosthenes is one of the most efficient ways to find all the prime number less than n.



        Implemenation of Algorithm






        share|cite|improve this answer









        $endgroup$
















          0












          0








          0





          $begingroup$

          The sieve of Eratosthenes is one of the most efficient ways to find all the prime number less than n.



          Implemenation of Algorithm






          share|cite|improve this answer









          $endgroup$



          The sieve of Eratosthenes is one of the most efficient ways to find all the prime number less than n.



          Implemenation of Algorithm







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered May 1 '16 at 11:52









          BadalBadal

          1




          1























              -1












              $begingroup$

              Odd numbers can be wheeled in multiplications to output only odd composite numbers. Then the odd numbers that are not output are the prime numbers.



              Now each inner loop can stop at a multiplication that reaches the value of an upper-bound and the outer loop can stop at the square root of the upper-bound.



              Furthermore the loops from the number 11 can increment with 2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10 ... as continuting and repeating. That's a big performance gain because multiples of 3, 5, and 7 are removed from the sequence of odd numbers.



              A prime number application really works best when outputting prime numbers between an upper bound and the upper bound - n. Then the application appears to be just scrolling sections (or jumping to sections) of a list on each computation. And in this case the loop increments are really only needed on the outer loop because a single division operation jumps over unneeded sections of the inner loop. Of course, array subscript locations can work with translations such that the same array can handle any of the segmented computations and then not use very much memory.






              share|cite|improve this answer











              $endgroup$


















                -1












                $begingroup$

                Odd numbers can be wheeled in multiplications to output only odd composite numbers. Then the odd numbers that are not output are the prime numbers.



                Now each inner loop can stop at a multiplication that reaches the value of an upper-bound and the outer loop can stop at the square root of the upper-bound.



                Furthermore the loops from the number 11 can increment with 2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10 ... as continuting and repeating. That's a big performance gain because multiples of 3, 5, and 7 are removed from the sequence of odd numbers.



                A prime number application really works best when outputting prime numbers between an upper bound and the upper bound - n. Then the application appears to be just scrolling sections (or jumping to sections) of a list on each computation. And in this case the loop increments are really only needed on the outer loop because a single division operation jumps over unneeded sections of the inner loop. Of course, array subscript locations can work with translations such that the same array can handle any of the segmented computations and then not use very much memory.






                share|cite|improve this answer











                $endgroup$
















                  -1












                  -1








                  -1





                  $begingroup$

                  Odd numbers can be wheeled in multiplications to output only odd composite numbers. Then the odd numbers that are not output are the prime numbers.



                  Now each inner loop can stop at a multiplication that reaches the value of an upper-bound and the outer loop can stop at the square root of the upper-bound.



                  Furthermore the loops from the number 11 can increment with 2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10 ... as continuting and repeating. That's a big performance gain because multiples of 3, 5, and 7 are removed from the sequence of odd numbers.



                  A prime number application really works best when outputting prime numbers between an upper bound and the upper bound - n. Then the application appears to be just scrolling sections (or jumping to sections) of a list on each computation. And in this case the loop increments are really only needed on the outer loop because a single division operation jumps over unneeded sections of the inner loop. Of course, array subscript locations can work with translations such that the same array can handle any of the segmented computations and then not use very much memory.






                  share|cite|improve this answer











                  $endgroup$



                  Odd numbers can be wheeled in multiplications to output only odd composite numbers. Then the odd numbers that are not output are the prime numbers.



                  Now each inner loop can stop at a multiplication that reaches the value of an upper-bound and the outer loop can stop at the square root of the upper-bound.



                  Furthermore the loops from the number 11 can increment with 2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10 ... as continuting and repeating. That's a big performance gain because multiples of 3, 5, and 7 are removed from the sequence of odd numbers.



                  A prime number application really works best when outputting prime numbers between an upper bound and the upper bound - n. Then the application appears to be just scrolling sections (or jumping to sections) of a list on each computation. And in this case the loop increments are really only needed on the outer loop because a single division operation jumps over unneeded sections of the inner loop. Of course, array subscript locations can work with translations such that the same array can handle any of the segmented computations and then not use very much memory.







                  share|cite|improve this answer














                  share|cite|improve this answer



                  share|cite|improve this answer








                  edited Dec 25 '18 at 21:14

























                  answered Dec 25 '18 at 20:46









                  S SpringS Spring

                  1723




                  1723

















                      protected by dxiv Dec 22 '17 at 6:46



                      Thank you for your interest in this question.
                      Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).



                      Would you like to answer one of these unanswered questions instead?



                      Popular posts from this blog

                      Probability when a professor distributes a quiz and homework assignment to a class of n students.

                      Aardman Animations

                      Are they similar matrix