<p>I want to print the first 10000 prime numbers.
Can anyone give me the most efficient code for this?
Clarifications:</p>

<ol>
<li>It does not matter if your code is inefficient for n >10000.</li>
<li>The size of the code does not matter.</li>
<li>You cannot just hard code the values in any manner.</li>
</ol>

[{'answer_id': 623, 'author': 'Matt', 'author_id': 154, 'author_profile': 'https://Stackoverflow.com/users/154', 'pm_score': 7, 'selected': True, 'text': '<p><a href="http://en.wikipedia.org/wiki/Sieve_of_Atkin" rel="noreferrer">The Sieve of Atkin</a> is probably what you\'re looking for, its upper bound running time is O(N/log log N).</p>\n\n<p>If you only run the numbers 1 more and 1 less than the multiples of 6, it could be even faster, as all prime numbers above 3 are 1 away from some multiple of six. \n<a href="http://primes.utm.edu/notes/faq/six.html" rel="noreferrer">Resource for my statement</a></p>\n'}, {'answer_id': 791, 'author': 'engtech', 'author_id': 175, 'author_profile': 'https://Stackoverflow.com/users/175', 'pm_score': 3, 'selected': False, 'text': '<p>Not efficient at all, but you can use a regular expression to test for prime numbers.</p>\n\n<pre><code>/^1?$|^(11+?)\\1+$/\n</code></pre>\n\n<p>This tests if, for a string consisting of <em>k</em> “<code>1</code>”s, <em>k</em> is <em>not prime</em> (i.e. whether the string consists of one “<code>1</code>” or any number of “<code>1</code>”s that can be expressed as an <em>n</em>-ary product).</p>\n'}, {'answer_id': 2753, 'author': 'GateKiller', 'author_id': 383, 'author_profile': 'https://Stackoverflow.com/users/383', 'pm_score': 3, 'selected': False, 'text': '<p>I have adapted code found on the <a href="http://www.codeproject.com/KB/recipes/highspeed_primenumbers.aspx" rel="nofollow noreferrer">CodeProject</a> to create the following:</p>\n\n<pre><code>ArrayList primeNumbers = new ArrayList();\n\nfor(int i = 2; primeNumbers.Count &lt; 10000; i++) {\n    bool divisible = false;\n\n    foreach(int number in primeNumbers) {\n        if(i % number == 0) {\n            divisible = true;\n        }\n    }\n\n    if(divisible == false) {\n        primeNumbers.Add(i);\n        Console.Write(i + " ");\n    }\n}\n</code></pre>\n\n<p>Testing this on my ASP.NET Server took the rountine about 1 minute to run.</p>\n'}, {'answer_id': 2967, 'author': 'num1', 'author_id': 306, 'author_profile': 'https://Stackoverflow.com/users/306', 'pm_score': 5, 'selected': False, 'text': '<p>I recommend a sieve, either the <a href="http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/" rel="noreferrer">Sieve of Eratosthenes</a> or the <a href="http://cr.yp.to/primegen.html" rel="noreferrer">Sieve of Atkin.</a>  </p>\n\n<p>The sieve or Eratosthenes is probably the most intuitive method of finding a list of primes. Basically you:</p>\n\n<ol>\n<li>Write down a list of numbers from 2 to whatever limit you want, let\'s say 1000.</li>\n<li>Take the first number that isn\'t crossed off (for the first iteration this is 2) and cross off all multiples of that number from the list.</li>\n<li>Repeat step 2 until you reach the end of the list. All the numbers that aren\'t crossed off are prime.</li>\n</ol>\n\n<p>Obviously there are quite a few optimizations that can be done to make this algorithm work faster, but this is the basic idea.</p>\n\n<p>The sieve of Atkin uses a similar approach, but unfortunately I don\'t know enough about it to explain it to you. But I do know that the algorithm I linked takes 8 seconds to figure out all the primes up to 1000000000 on an ancient Pentium II-350</p>\n\n<p>Sieve of Eratosthenes Source Code: <a href="http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/" rel="noreferrer">http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/</a></p>\n\n<p>Sieve of Atkin Source Code: <a href="http://cr.yp.to/primegen.html" rel="noreferrer">http://cr.yp.to/primegen.html</a></p>\n'}, {'answer_id': 19088, 'author': 'Imran', 'author_id': 1897, 'author_profile': 'https://Stackoverflow.com/users/1897', 'pm_score': 2, 'selected': False, 'text': '<p><a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow noreferrer">Sieve of Eratosthenes</a> is the way to go, because of it\'s simplicity and speed. My implementation in C</p>\n\n<pre><code>#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n#include &lt;stdbool.h&gt;\n#include &lt;math.h&gt;\n\nint main(void)\n{\n    unsigned int lim, i, j;\n\n    printf("Find primes upto: ");\n    scanf("%d", &amp;lim);\n    lim += 1;\n    bool *primes = calloc(lim, sizeof(bool));\n\n    unsigned int sqrtlim = sqrt(lim);\n    for (i = 2; i &lt;= sqrtlim; i++)\n        if (!primes[i])\n            for (j = i * i; j &lt; lim; j += i)\n                primes[j] = true;\n\n    printf("\\nListing prime numbers between 2 and %d:\\n\\n", lim - 1);\n    for (i = 2; i &lt; lim; i++)\n        if (!primes[i])\n            printf("%d\\n", i);\n\n    return 0;\n}\n</code></pre>\n\n<p>CPU Time to find primes (on Pentium Dual Core E2140 1.6 GHz, using single core)</p>\n\n<blockquote>\n  <p>~ 4s for lim = 100,000,000</p>\n</blockquote>\n'}, {'answer_id': 31176, 'author': 'palotasb', 'author_id': 3063, 'author_profile': 'https://Stackoverflow.com/users/3063', 'pm_score': 4, 'selected': False, 'text': '<p><a href="https://stackoverflow.com/questions/622/most-efficient-code-for-the-first-10000-prime-numbers#2753">GateKiller</a>, how about adding a <code>break</code> to that <code>if</code> in the <code>foreach</code> loop? That would speed up things <strong>a lot</strong> because if like 6 is divisible by 2 you don\'t need to check with 3 and 5. (I\'d vote your solution up anyway if I had enough reputation :-) ...)</p>\n\n<pre><code>ArrayList primeNumbers = new ArrayList();\n\nfor(int i = 2; primeNumbers.Count &lt; 10000; i++) {\n    bool divisible = false;\n\n    foreach(int number in primeNumbers) {\n        if(i % number == 0) {\n            divisible = true;\n            break;\n        }\n    }\n\n    if(divisible == false) {\n        primeNumbers.Add(i);\n        Console.Write(i + " ");\n    }\n}\n</code></pre>\n'}, {'answer_id': 34090, 'author': 'hoyhoy', 'author_id': 3499, 'author_profile': 'https://Stackoverflow.com/users/3499', 'pm_score': 3, 'selected': False, 'text': '<p>Using GMP, one could write the following:</p>\n\n<pre><code>#include &lt;stdio.h&gt;\n#include &lt;gmp.h&gt;\n\nint main() {\n  mpz_t prime;\n  mpz_init(prime);\n  mpz_set_ui(prime, 1);\n  int i;\n  char* num = malloc(4000);\n  for(i=0; i&lt;10000; i++) {\n    mpz_nextprime(prime, prime);\n    printf("%s, ", mpz_get_str(NULL,10,prime));\n  }\n}\n</code></pre>\n\n<p>On my 2.33GHz Macbook Pro, it executes as follows:</p>\n\n<pre><code>time ./a.out &gt; /dev/null\n\nreal    0m0.033s\nuser    0m0.029s\nsys    0m0.003s\n</code></pre>\n\n<p>Calculating 1,000,000 primes on the same laptop:</p>\n\n<pre><code>time ./a.out &gt; /dev/null\n\nreal    0m14.824s\nuser    0m14.606s\nsys     0m0.086s\n</code></pre>\n\n<p>GMP is highly optimized for this sort of thing.  Unless you really want to understand the algorithms by writing your own, you\'d be advised to use libGMP under C.</p>\n'}, {'answer_id': 37182, 'author': 'John with waffle', 'author_id': 279, 'author_profile': 'https://Stackoverflow.com/users/279', 'pm_score': 4, 'selected': False, 'text': '<p>This isn\'t strictly against the hardcoding restriction, but comes terribly close.  Why not programatically download this list and print it out, instead?</p>\n\n<p><a href="http://primes.utm.edu/lists/small/10000.txt" rel="noreferrer">http://primes.utm.edu/lists/small/10000.txt</a></p>\n'}, {'answer_id': 175956, 'author': 'jfs', 'author_id': 4279, 'author_profile': 'https://Stackoverflow.com/users/4279', 'pm_score': 4, 'selected': False, 'text': '<p>@Matt: log(log(10000)) is ~2</p>\n\n<p>From the wikipedia article (which you cited) <a href="http://en.wikipedia.org/wiki/Sieve_of_Atkin" rel="noreferrer">Sieve of Atkin</a>:</p>\n\n<blockquote>\n  <p>This sieve computes primes up to N\n  using <code>O(N/log log N)</code> operations with\n  only N<sup>1/2+o(1)</sup> bits of memory. That is\n  a little better than the sieve of\n  Eratosthenes which uses <code>O(N)</code>\n  operations and O(N<sup>1/2</sup>(log log N)/log\n  N) bits of memory <a href="http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf" rel="noreferrer">(A.O.L. Atkin, D.J. Bernstein, 2004)</a>. These asymptotic\n  computational complexities include\n  simple optimizations, such as wheel\n  factorization, and splitting the\n  computation to smaller blocks.</p>\n</blockquote>\n\n<p>Given asymptotic computational complexities along <code>O(N)</code> (for Eratosthenes) and <code>O(N/log(log(N)))</code> (for Atkin) we can\'t say (for small <code>N=10_000</code>) which algorithm if implemented will be faster.</p>\n\n<p>Achim Flammenkamp wrote in <a href="http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html" rel="noreferrer">The Sieve of Eratosthenes</a>:</p>\n\n<p>cited by:</p>\n\n<p>@num1</p>\n\n<blockquote>\n  <p>For intervals larger about 10^9,\n  surely for those > 10^10, the Sieve of\n  Eratosthenes is outperformed by the\n  Sieve of Atkins and Bernstein which\n  uses irreducible binary quadratic\n  forms. See their paper for background\n  informations as well as paragraph 5 of\n  W. Galway\'s Ph.D. thesis.</p>\n</blockquote>\n\n<p>Therefore for <code>10_000</code> Sieve of Eratosthenes can be faster then Sieve of Atkin.</p>\n\n<p>To answer OP the code is <a href="http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.c" rel="noreferrer">prime_sieve.c</a> (cited by <code>num1</code>) </p>\n'}, {'answer_id': 552319, 'author': 'Pat Hermens', 'author_id': 1677, 'author_profile': 'https://Stackoverflow.com/users/1677', 'pm_score': 2, 'selected': False, 'text': '<p>Adapting and following on from <a href="https://stackoverflow.com/questions/622/most-efficient-code-for-the-first-10000-prime-numbers/2753#2753">GateKiller</a>, here\'s the final version that I\'ve used.</p>\n\n<pre><code>    public IEnumerable&lt;long&gt; PrimeNumbers(long number)\n    {\n        List&lt;long&gt; primes = new List&lt;long&gt;();\n        for (int i = 2; primes.Count &lt; number; i++)\n        {\n            bool divisible = false;\n\n            foreach (int num in primes)\n            {\n                if (i % num == 0)\n                    divisible = true;\n\n                if (num &gt; Math.Sqrt(i))\n                    break;\n            }\n\n            if (divisible == false)\n                primes.Add(i);\n        }\n        return primes;\n    }\n</code></pre>\n\n<p>It\'s basically the same, but I\'ve added the "break on Sqrt" suggestion and changed some of the variables around to make it fit better for me. (I was working on Euler and needed the 10001th prime)</p>\n'}, {'answer_id': 1019318, 'author': 'Sumit Kishore', 'author_id': 107434, 'author_profile': 'https://Stackoverflow.com/users/107434', 'pm_score': 2, 'selected': False, 'text': "<p>The Sieve seems to be the wrong answer. The sieve gives you the primes <strong>up to</strong> a number <strong>N</strong>, not the <strong>first N</strong> primes. Run @Imran or @Andrew Szeto, and you get the primes up to N. </p>\n\n<p>The sieve might still be usable if you keep trying sieves for increasingly larger numbers until you hit a certain size of your result set, and use some caching of numbers already obtained, but I believe it would still be no faster than a solution like @Pat's.</p>\n"}, {'answer_id': 1390584, 'author': 'Eric Schoonover', 'author_id': 3957, 'author_profile': 'https://Stackoverflow.com/users/3957', 'pm_score': 2, 'selected': False, 'text': '<p>Here is a Sieve of Eratosthenes that I wrote in PowerShell a few days ago.  It has a parameter for identifying the number of prime numbers that should be returned.</p>\n\n<pre><code>#\n# generate a list of primes up to a specific target using a sieve of eratosthenes\n#\nfunction getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes\n    param ($target,$count = 0)\n    $sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target\n    $sieve = @($false) * $sieveBound\n    $crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)\n    for ($i = 1; $i -le $crossLimit; $i ++) {\n        if ($sieve[$i] -eq $false) {\n            $prime = 2 * $i + 1\n            write-debug "Found: $prime"\n            for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {\n                $sieve[$x] = $true\n            }\n        }\n    }\n    $primes = @(2)\n    for ($i = 1; $i -le $sieveBound; $i ++) {\n        if($count -gt 0 -and $primes.length -ge $count) {\n            break;\n        }\n        if($sieve[$i] -eq $false) {\n            $prime = 2 * $i + 1\n            write-debug "Output: $prime"\n            $primes += $prime\n        }\n    }\n    return $primes\n}\n</code></pre>\n'}, {'answer_id': 2309490, 'author': 'John La Rooy', 'author_id': 174728, 'author_profile': 'https://Stackoverflow.com/users/174728', 'pm_score': 1, 'selected': False, 'text': '<p>In Python</p>\n\n<pre><code>import gmpy\np=1\nfor i in range(10000):\n    p=gmpy.next_prime(p)\n    print p \n</code></pre>\n'}, {'answer_id': 4540559, 'author': 'Brijesh', 'author_id': 555202, 'author_profile': 'https://Stackoverflow.com/users/555202', 'pm_score': 0, 'selected': False, 'text': '<p>I have written this using python, as I just started learning it, and it works perfectly fine. The 10,000th prime generate by this code as same as mentioned in <a href="http://primes.utm.edu/lists/small/10000.txt" rel="nofollow">http://primes.utm.edu/lists/small/10000.txt</a>. To check if <code>n</code> is prime or not, divide <code>n</code> by the numbers from <code>2</code> to <code>sqrt(n)</code>. If any of this range of number perfectly divides <code>n</code> then it\'s not prime.</p>\n\n<pre><code>import math\nprint ("You want prime till which number??")\na = input()\na = int(a)\nx = 0\nx = int(x)\ncount = 1\nprint("2 is prime number")\nfor c in range(3,a+1):\n    b = math.sqrt(c)\n    b = int(b)\n    x = 0\n    for b in range(2,b+1):\n        e  = c % b\n        e = int(e)\n        if (e == 0):\n            x = x+1\n    if (x == 0):\n        print("%d is prime number" % c)\n        count = count + 1\nprint("Total number of prime till %d is %d" % (a,count))\n</code></pre>\n'}, {'answer_id': 5268325, 'author': 'Chris Stevenson', 'author_id': 654631, 'author_profile': 'https://Stackoverflow.com/users/654631', 'pm_score': 1, 'selected': False, 'text': '<p>Here is my VB 2008 code, which finds all primes &lt;10,000,000 in 1 min 27 secs on my work laptop. It skips even numbers and only looks for primes that are &lt; the sqrt of the test number. It is only designed to find primes from 0 to a sentinal value.</p>\n\n<pre><code>Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles \nButton1.Click\n\n    Dim TestNum As Integer\n    Dim X As Integer\n    Dim Z As Integer\n    Dim TM As Single\n    Dim TS As Single\n    Dim TMS As Single\n    Dim UnPrime As Boolean\n    Dim Sentinal As Integer\n    Button1.Text = "Thinking"\n    Button1.Refresh()\n    Sentinal = Val(SentinalTxt.Text)\n    UnPrime = True\n    Primes(0) = 2\n    Primes(1) = 3\n    Z = 1\n    TM = TimeOfDay.Minute\n    TS = TimeOfDay.Second\n    TMS = TimeOfDay.Millisecond\n    For TestNum = 5 To Sentinal Step 2\n        Do While Primes(X) &lt;&gt; 0 And UnPrime And Primes(X) ^ 2 &lt;= TestNum\n            If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then\n                UnPrime = False\n            End If\n            X = X + 1\n\n        Loop\n        If UnPrime = True Then\n            X = X + 1\n            Z = Z + 1\n            Primes(Z) = TestNum\n        End If\n        UnPrime = True\n        X = 0\n    Next\n    Button1.Text = "Finished with " &amp; Z\n    TM = TimeOfDay.Minute - TM\n    TS = TimeOfDay.Second - TS\n    TMS = TimeOfDay.Millisecond - TMS\n    ShowTime.Text = TM &amp; ":" &amp; TS &amp; ":" &amp; TMS\nEnd Sub\n</code></pre>\n'}, {'answer_id': 10287195, 'author': 'namibj', 'author_id': 1352184, 'author_profile': 'https://Stackoverflow.com/users/1352184', 'pm_score': 0, 'selected': False, 'text': '<p>I spend some time writing a program calculating a lot of primes and this is the code I\'m used to calculate a text file containing the first 1.000.000.000 primes. It\'s in German, but the interesting part is the method <code>calcPrimes()</code>. The primes are stored in an array called Primzahlen. I recommend a 64bit CPU because the calculations are with 64bit integers.</p>\n\n<pre><code>import java.io.*;\nclass Primzahlengenerator {\n    long[] Primzahlen;\n    int LastUnknown = 2;\n    public static void main(String[] args)  {\n        Primzahlengenerator Generator = new Primzahlengenerator();\n        switch(args.length) {\n            case 0:  //Wenn keine Argumente übergeben worden:\n                Generator.printHelp(); //Hilfe ausgeben\n                return; //Durchfallen verhindern\n            case 1:\n                try {\n                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];\n                }\n                catch (NumberFormatException e) {\n                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \\"Tausend\\", sondern in Ziffern z.B. \\"1000\\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben\n                    Generator.printHelp();                    //Generelle Hilfe ausgeben\n                    return;\n                }\n                break;//dutchfallen verhindern\n\n            case 2:\n                switch (args[1]) {\n                    case "-l":\n                        System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben\n                        Generator.printHelp();                                    //Generelle Hilfe ausgeben\n                        return;\n                }\n                break;//durchfallen verhindern\n            case 3:\n                try {\n                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];\n                }\n                catch (NumberFormatException e) {\n                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \\"Tausend\\", sondern in Ziffern z.B. \\"1000\\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben\n                    Generator.printHelp();                      //Generelle Hilfe ausgeben\n                    return;\n                }\n                switch(args[1]) {\n                    case "-l":\n                        Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist\n                        break;\n                    default:\n                        Generator.printHelp();\n                        break;\n                }\n                break;\n            default:\n                Generator.printHelp();\n                return;\n        }\n        Generator.calcPrims();\n    }\n    void printHelp() {\n        System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen.");   //Anleitung wie man das Programm mit Argumenten füttern muss\n        System.out.println("Als zweites Argument können sie \\"-l\\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");\n        System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \\"java Primzahlengenerator 1000 &gt; Primzahlen.txt\\" entsteht.");\n    }\n    void loadFromFile(String File) {\n        // System.out.println("Lese Datei namens: \\"" + File + "\\"");\n        try{\n            int x = 0;\n            BufferedReader in = new BufferedReader(new FileReader(File));\n            String line;\n            while((line = in.readLine()) != null) {\n                Primzahlen[x] = new Long(line).longValue();\n                x++;\n            }\n            LastUnknown = x;\n        } catch(FileNotFoundException ex) {\n            System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");\n        } catch(IOException ex) {\n            System.err.println(ex);\n        } catch(ArrayIndexOutOfBoundsException ex) {\n            System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");\n            System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");\n            }\n        /* for(long prim : Primzahlen) {\n            System.out.println("" + prim);\n        } */\n        //Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:\n        //java Primzahlengenerator 1000 &gt; 1000Primzahlen.txt\n        //da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();\n        //erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.\n        //falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:\n        //int[] foo = { 1, 2, 3};\n        //int bar = foo[4];\n        //dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.\n    }\n    void calcPrims() {\n        int PrimzahlNummer = LastUnknown;\n        // System.out.println("LAstUnknown ist: " + LastUnknown);\n        Primzahlen[0] = 2;\n        Primzahlen[1] = 3;\n        long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];\n        boolean IstPrimzahl;\n        // System.out.println("2");\n        // System.out.println("3");\n        int Limit = Primzahlen.length;\n        while(PrimzahlNummer &lt; Limit) {\n            IstPrimzahl = true;\n            double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);\n            for(int i = 1;i &lt; PrimzahlNummer;i++) {\n                if(AktuelleZahl % Primzahlen[i] == 0) {\n                    IstPrimzahl = false;\n                    break;\n                }\n                if(Primzahlen[i] &gt; WurzelDerAktuellenZahl) break;\n            }\n            if(IstPrimzahl) {\n                Primzahlen[PrimzahlNummer] = AktuelleZahl;\n                PrimzahlNummer++;\n                // System.out.println("" + AktuelleZahl);\n            }\n            AktuelleZahl = AktuelleZahl + 2;\n        }\n        for(long prim : Primzahlen) {\n            System.out.println("" + prim);\n        }\n    }\n}\n</code></pre>\n'}, {'answer_id': 10302076, 'author': 'Will Ness', 'author_id': 849891, 'author_profile': 'https://Stackoverflow.com/users/849891', 'pm_score': 4, 'selected': False, 'text': '<p>In Haskell, we can write down almost word for word the mathematical definition of the sieve of Eratosthenes, "<em>primes are natural numbers above 1 without any composite numbers, where composites are found by enumeration of each prime\'s multiples</em>":</p>\n\n<pre class="lang-hs prettyprint-override"><code>import Data.List.Ordered (minus, union)\n\nprimes = 2 : minus [3..] (foldr (\\p r -&gt; p*p : union [p*p+p, p*p+2*p..] r)\n                                [] primes)\n</code></pre>\n\n<p><code>primes !! 10000</code> is near-instantaneous. </p>\n\n<p>References:</p>\n\n<ul>\n<li><a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow noreferrer">Sieve of Eratosthenes</a></li>\n<li><a href="http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf" rel="nofollow noreferrer">Richard Bird\'s sieve (see pp. 10,11)</a></li>\n<li><a href="http://www.haskell.org/haskellwiki/Prime_numbers#Initial_definition" rel="nofollow noreferrer">minus, union</a></li>\n</ul>\n\n<hr>\n\n<p><sub>The above code is easily tweaked into working on odds only, <strong><code>primes = 2 : 3 : minus [5,7..] (foldr (\\p r -&gt; p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes))</code></strong>. Time complexity is much improved (to just about a <em>log</em> factor above optimal) by folding in a tree-like structure, and space complexity is <a href="http://ideone.com/se0bsB" rel="nofollow noreferrer">drastically improved</a> by <a href="https://stackoverflow.com/questions/13894417/double-stream-feed-to-prevent-unneeded-memoization/13895347#13895347">multistage primes production</a>, in</sub></p>\n\n<pre class="lang-hs prettyprint-override"><code>primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\\p -&gt; [p*p, p*p+2*p..]) )\n  where\n    _Y g = g (_Y g)                        -- non-sharing fixpoint combinator\n    _U ((x:xs):t) = x : (union xs . _U . pairs) t       -- ~= nub.sort.concat\n    pairs    (xs:ys:t)  = union xs ys : pairs t\n    sieve k s@(x:xs) | k &lt; x      = k : sieve (k+2) s   -- ~= [k,k+2..]\\\\s,\n                     | otherwise  =     sieve (k+2) xs  --   when s⊂[k,k+2..]\n</code></pre>\n\n<p><sub>(In Haskell the parentheses are used for grouping, a function call is signified just by juxtaposition, <strong><code>(:)</code></strong> is a <em>cons</em> operator for lists, and <strong><code>(.)</code></strong> is a functional composition operator: <strong><code>(f . g) x = (\\y -&gt; f (g y)) x = f (g x)</code></strong>).</sub></p>\n'}, {'answer_id': 10492469, 'author': 'Sumanth', 'author_id': 1381156, 'author_profile': 'https://Stackoverflow.com/users/1381156', 'pm_score': -1, 'selected': False, 'text': '<pre><code>using System;\n\nnamespace ConsoleApplication2\n{\n    class Program\n    {\n        static void Main(string[] args)\n        {\n            int n, i = 3, j, c;\n            Console.WriteLine("Please enter your integer: ");\n            n = Convert.ToInt32(Console.ReadLine());\n            if (n &gt;= 1)\n            {\n                Console.WriteLine("First " + n + " Prime Numbers are");\n                Console.WriteLine("2");\n            }\n            for(j=2;j&lt;=n;)\n            {\n                for(c=2;c&lt;=i-1;c++)\n                {\n                    if(i%c==0)\n                        break;\n                }\n                    if(c==i)\n                    {\n                        Console.WriteLine(i);\n                        j++;\n                    }\n                    i++;                                \n            }\n            Console.Read();\n        }\n    }\n}\n</code></pre>\n'}, {'answer_id': 22122651, 'author': 'Roger Doering', 'author_id': 3369685, 'author_profile': 'https://Stackoverflow.com/users/3369685', 'pm_score': 1, 'selected': False, 'text': '<p>The following Mathcad code calculated the first million primes in under 3 minutes.</p>\n\n<p>Bear in mind that this would be using floating point doubles for all of the numbers and is basically interpreted. I hope the syntax is clear.</p>\n\n<p><img src="https://i.stack.imgur.com/51jJq.jpg" alt="enter image description here"></p>\n'}, {'answer_id': 36668089, 'author': 'BenGoldberg', 'author_id': 3093194, 'author_profile': 'https://Stackoverflow.com/users/3093194', 'pm_score': 1, 'selected': False, 'text': '<p>Here is a C++ solution, using a form of SoE:</p>\n\n<pre><code>#include &lt;iostream&gt;\n#include &lt;deque&gt;\n\ntypedef std::deque&lt;int&gt; mydeque;\n\nvoid my_insert( mydeque &amp; factors, int factor ) {\n    int where = factor, count = factors.size();\n    while( where &lt; count &amp;&amp; factors[where] ) where += factor;\n    if( where &gt;= count ) factors.resize( where + 1 );\n    factors[ where ] = factor;\n}\n\nint main() {\n    mydeque primes;\n    mydeque factors;\n    int a_prime = 3, a_square_prime = 9, maybe_prime = 3;\n    int cnt = 2;\n    factors.resize(3);\n    std::cout &lt;&lt; "2 3 ";\n\n    while( cnt &lt; 10000 ) {\n        int factor = factors.front();\n        maybe_prime += 2;\n        if( factor ) {\n            my_insert( factors, factor );\n        } else if( maybe_prime &lt; a_square_prime ) {\n            std::cout &lt;&lt; maybe_prime &lt;&lt; " ";\n            primes.push_back( maybe_prime );\n            ++cnt;\n        } else {\n            my_insert( factors, a_prime );\n            a_prime = primes.front();\n            primes.pop_front();\n            a_square_prime = a_prime * a_prime;\n        }\n        factors.pop_front();\n    }\n\n    std::cout &lt;&lt; std::endl;\n    return 0;\n}\n</code></pre>\n\n<p>Note that this version of the Sieve can compute primes indefinitely.</p>\n\n<p>Also note, the STL <code>deque</code> takes <code>O(1)</code> time to perform <code>push_back</code>, <code>pop_front</code>, and random access though subscripting.</p>\n\n<p>The <code>resize</code> operation takes <code>O(n)</code> time, where <code>n</code> is the number of elements being added.  Due to how we are using this function, we can treat this is a small constant.</p>\n\n<p>The body of the <code>while</code> loop in <code>my_insert</code> is executed <code>O(log log n)</code> times, where <code>n</code> equals the variable <code>maybe_prime</code>.  This is because the condition expression of the <code>while</code> will evaluate to true once for each prime factor of <code>maybe_prime</code>.  See "<a href="https://en.wikipedia.org/wiki/Divisor_function" rel="nofollow" title="Divisor function">Divisor function</a>" on Wikipedia.</p>\n\n<p>Multiplying by the number of times <code>my_insert</code> is called, shows that it should take <code>O(n log log n)</code> time to list <code>n</code> primes... which is, unsurprisingly, the time complexity which the Sieve of Eratosthenes is supposed to have.</p>\n\n<p>However, while this code <strong>is</strong> efficient, it\'s not the <strong>most efficient</strong>... I would strongly suggest using a specialized library for primes generation, such as <a href="http://primesieve.org/" rel="nofollow" title="primesieve">primesieve</a>.  Any truly efficient, well optimized solution, will take more code than anyone wants to type into Stackoverflow.</p>\n'}, {'answer_id': 36725003, 'author': 'DarthGizka', 'author_id': 4156577, 'author_profile': 'https://Stackoverflow.com/users/4156577', 'pm_score': 2, 'selected': False, 'text': '<p>The <a href="https://stackoverflow.com/a/36668089/4156577">deque sieve algorithm mentioned by BenGoldberg</a> deserves a closer look, not only because it is very elegant but also because it can occasionally be useful in practice (unlike the Sieve of Atkin, which is a purely academical exercise).</p>\n\n<p>The basic idea behind the deque sieve algorithm is to use a small, sliding sieve that is only large enough to contain at least one separate multiple for each of the currently \'active\' prime factors - i.e. those primes whose square does not exceed the lowest number currently represented by the moving sieve. Another difference to the SoE is that the deque sieve stores the actual factors into the slots of composites, not booleans.</p>\n\n<p>The algorithm extends the size of the sieve window as needed, resulting in fairly even performance over a wide range until the sieve starts exceeding the capacity of the CPU\'s L1 cache appreciably. The last prime that fits fully is 25,237,523 (the 1,579,791st prime), which gives a rough ballpark figure for the reasonable operating range of the algorithm.</p>\n\n<p>The algorithm is fairly simple and robust, and it has even performance over a much wider range than an unsegmented Sieve of Eratosthenes. The latter is a lot faster as long its sieve fits fully into the cache, i.e. up to 2^16 for an odds-only sieve with byte-sized bools. Then its performance drops more and more, although it always remains significantly faster than the deque despite the handicap (at least in compiled languages like C/C++, Pascal or Java/C#).</p>\n\n<p>Here is a rendering of the deque sieve algorithm in C#, because I find that language - despite its many flaws - much more practical for prototyping algorithms and experimentation than the supremely cumbersome and pedantic C++. <em>(Sidenote: I\'m using the free <a href="https://www.linqpad.net/" rel="nofollow noreferrer">LINQPad</a> which makes it possible to dive right in, without all the messiness with setting up projects, makefiles, directories or whatnot, and it gives me the same degree of interactivity as a python prompt).</em></p>\n\n<p>C# doesn\'t have an explicit deque type but the plain <code>List&lt;int&gt;</code> works well enough for demonstrating the algorithm. </p>\n\n<p>Note: this version does not use a deque for the primes, because it simply doesn\'t make sense to pop off sqrt(n) out of n primes. What good would it be to remove 100 primes and to leave 9900? At least this way all the primes are collected in a neat vector, ready for further processing.</p>\n\n\n\n<pre class="lang-cs prettyprint-override"><code>static List&lt;int&gt; deque_sieve (int n = 10000)\n{\n    Trace.Assert(n &gt;= 3);\n\n    var primes = new List&lt;int&gt;()  {  2, 3  };\n    var sieve = new List&lt;int&gt;()  {  0, 0, 0  };\n\n    for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )\n    {\n        int base_factor = sieve[0];\n\n        if (base_factor != 0)\n        {\n            // the sieve base has a non-trivial factor - put that factor back into circulation\n            mark_next_unmarked_multiple(sieve, base_factor);\n        }\n        else if (sieve_base &lt; current_prime_squared)  // no non-trivial factor -&gt; found a non-composite\n        {\n            primes.Add(sieve_base);\n\n            if (primes.Count == n)\n                return primes;\n        }\n        else // sieve_base == current_prime_squared\n        {\n            // bring the current prime into circulation by injecting it into the sieve ...\n            mark_next_unmarked_multiple(sieve, primes[current_prime_index]);\n\n            // ... and elect a new current prime\n            current_prime_squared = square(primes[++current_prime_index]);\n        }\n\n        // slide the sieve one step forward\n        sieve.RemoveAt(0);  sieve_base += 2;\n    }\n}\n</code></pre>\n\n<p>Here are the two helper functions:</p>\n\n<pre class="lang-cs prettyprint-override"><code>static void mark_next_unmarked_multiple (List&lt;int&gt; sieve, int prime)\n{\n    int i = prime, e = sieve.Count;\n\n    while (i &lt; e &amp;&amp; sieve[i] != 0)\n        i += prime;\n\n    for ( ; e &lt;= i; ++e)  // no List&lt;&gt;.Resize()...\n        sieve.Add(0);\n\n    sieve[i] = prime;\n}\n\nstatic int square (int n)\n{\n    return n * n;\n}\n</code></pre>\n\n<p>Probably the easiest way of understanding the algorithm is to imagine it as a special segmented Sieve of Eratosthenes with a segment size of 1, accompanied by an overflow area where the primes come to rest when they shoot over the end of the segment. Except that the single cell of the segment (a.k.a. <code>sieve[0]</code>) has already been sieved when we get to it, because it got run over while it was part of the overflow area.</p>\n\n<p>The number that is represented by <code>sieve[0]</code> is held in <code>sieve_base</code>, although <code>sieve_front</code> or <code>window_base</code> would also be a good names that allow to draw parallels to Ben\'s code or implementations of segmented/windowed sieves.</p>\n\n<p>If <code>sieve[0]</code> contains a non-zero value then that value is a factor of <code>sieve_base</code>, which can thus be recognised as composite. Since cell 0 is a multiple of that factor it is easy to compute its next hop, which is simply 0 plus that factor. Should that cell be occupied already by another factor then we simply add the factor again, and so on until we find a multiple of the factor where no other factor is currently parked (extending the sieve if needed). This also means that there is no need for storing the current working offsets of the various primes from one segment to the next, as in a normal segmented sieve. Whenever we find a factor in <code>sieve[0]</code>, its current working offset is 0.</p>\n\n<p>The current prime comes into play in the following way. A prime can only become current after its own occurrence in the stream (i.e. when it has been detected as a prime, because not marked with a factor), and it will remain current until the exact moment that <code>sieve[0]</code> reaches its square. All lower multiples of this prime must have been struck off due to the activities of smaller primes, just like in a normal SoE. But none of the smaller primes can strike off the square, since the only factor of the square is the prime itself and it is not yet in circulation at this point. That explains the actions taken by the algorithm in the case <code>sieve_base == current_prime_squared</code> (which implies <code>sieve[0] == 0</code>, by the way).</p>\n\n<p>Now the case <code>sieve[0] == 0 &amp;&amp; sieve_base &lt; current_prime_squared</code> is easily explained: it means that <code>sieve_base</code> cannot be a multiple of any of the primes smaller than the current prime, or else it would have been marked as composite. I cannot be a higher multiple of the current prime either, since its value is less than the current prime\'s square. Hence it must be a new prime.</p>\n\n<p>The algorithm is obviously inspired by the Sieve of Eratosthenes, but equally obviously it is very different. The Sieve of Eratosthenes derives its superior speed from the simplicity of its elementary operations: one single index addition and one store for each step of the operation is all that it does for long stretches of time. </p>\n\n<p>Here is a simple, unsegmented Sieve of Eratosthenes that I normally use for sieving factor primes in the ushort range, i.e. up to 2^16. For this post I\'ve modified it to work beyond 2^16 by substituting <code>int</code> for <code>ushort</code></p>\n\n<pre class="lang-cs prettyprint-override"><code>static List&lt;int&gt; small_odd_primes_up_to (int n)\n{\n    var result = new List&lt;int&gt;();\n\n    if (n &lt; 3)\n        return result;\n\n    int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) &gt;&gt; 1, max_bit = (n - 1) &gt;&gt; 1;\n    var odd_composite = new bool[max_bit + 1];\n\n    for (int i = 3 &gt;&gt; 1; i &lt;= sqrt_n_halved; ++i)\n        if (!odd_composite[i])\n            for (int p = (i &lt;&lt; 1) + 1, j = p * p &gt;&gt; 1; j &lt;= max_bit; j += p)\n                odd_composite[j] = true;\n\n    result.Add(3);  // needs to be handled separately because of the mod 3 wheel\n\n    // read out the sieved primes\n    for (int i = 5 &gt;&gt; 1, d = 1; i &lt;= max_bit; i += d, d ^= 3)\n        if (!odd_composite[i])\n            result.Add((i &lt;&lt; 1) + 1);\n\n    return result;\n}\n</code></pre>\n\n<p>When sieving the first 10000 primes a typical L1 cache of 32 KiByte will be exceeded but the function is still very fast (fraction of a millisecond even in C#). </p>\n\n<p>If you compare this code to the deque sieve then it is easy to see that the operations of the deque sieve are a lot more complicated, and it cannot effectively amortise its overhead because it always does the shortest possible stretch of crossings-off in a row (exactly one single crossing-off, after skipping all multiples that have been crossed off already).</p>\n\n<p>Note: the C# code uses <code>int</code> instead of <code>uint</code> because newer compilers have a habit of generating substandard code for <code>uint</code>, probably in order to push people towards signed integers... In the C++ version of the code above I used <code>unsigned</code> throughout, naturally; the benchmark had to be in C++ because I wanted it be based on a supposedly adequate deque type (<code>std::deque&lt;unsigned&gt;</code>; there was no performance gain from using <code>unsigned short</code>). Here are the numbers for my Haswell laptop (VC++ 2015/x64):</p>\n\n<pre class="lang-none prettyprint-override"><code>deque vs simple: 1.802 ms vs 0.182 ms\ndeque vs simple: 1.836 ms vs 0.170 ms \ndeque vs simple: 1.729 ms vs 0.173 ms\n</code></pre>\n\n<p>Note: the C# times are pretty much exactly double the C++ timings, which is pretty good for C# and ìt shows that <code>List&lt;int&gt;</code> is no slouch even if abused as a deque.</p>\n\n<p>The simple sieve code still blows the deque out of the water, even though it is already operating beyond its normal working range (L1 cache size exceeded by 50%, with attendant cache thrashing). The dominating part here is the reading out of the sieved primes, and this is not affected much by the cache problem. In any case the function was designed for sieving the factors of factors, i.e. level 0 in a 3-level sieve hierarchy, and typically it has to return only a few hundred factors or a low number of thousands. Hence its simplicity.</p>\n\n<p>Performance could be improved by more than an order of magnitude by using a segmented sieve and optimising the code for extracting the sieved primes (stepped mod 3 and unrolled twice, or mod 15 and unrolled once) , and yet more performance could be squeezed out of the code by using a mod 16 or mod 30 wheel with all the trimmings (i.e. full unrolling for all residues). Something like that is explained in my answer to <a href="https://codereview.stackexchange.com/a/125057/56653">Find prime positioned prime number</a> over on Code Review, where a similar problem was discussed. But it\'s hard to see the point in improving sub-millisecond times for a one-off task...</p>\n\n<p>To put things a bit into perspective, here are the C++ timings for sieving up to 100,000,000:</p>\n\n<pre class="lang-none prettyprint-override"><code>deque vs simple: 1895.521 ms vs 432.763 ms\ndeque vs simple: 1847.594 ms vs 429.766 ms\ndeque vs simple: 1859.462 ms vs 430.625 ms\n</code></pre>\n\n<p>By contrast, a segmented sieve in C# with a few bells and whistles does the same job in 95 ms (no C++ timings available, since I do code challenges only in C# at the moment).</p>\n\n<p>Things may look decidedly different in an interpreted language like Python where every operation has a heavy cost and the interpreter overhead dwarfs all differences due to predicted vs. mispredicted branches or sub-cycle ops (shift, addition) vs. multi-cycle ops (multiplication, and perhaps even division). That is bound to erode the simplicity advantage of the Sieve of Eratosthenes, and this could make the deque solution a bit more attractive.</p>\n\n<p>Also, many of the timings reported by other respondents in this topic are probably dominated by <strong>output time</strong>. That\'s an entirely different war, where my main weapon is a simple class like this:</p>\n\n<pre class="lang-cs prettyprint-override"><code>class CCWriter\n{\n    const int SPACE_RESERVE = 11;  // UInt31 + \'\\n\'\n\n    public static System.IO.Stream BaseStream;\n    static byte[] m_buffer = new byte[1 &lt;&lt; 16];  // need 55k..60k for a maximum-size range\n    static int m_write_pos = 0;\n    public static long BytesWritten = 0;         // for statistics\n\n    internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();\n\n    internal static ushort[] create_double_digit_lookup ()\n    {\n        var lookup = new ushort[100];\n\n        for (int lo = 0; lo &lt; 10; ++lo)\n            for (int hi = 0; hi &lt; 10; ++hi)\n                lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi &lt;&lt; 8) + lo);\n\n        return lookup;\n    }\n\n    public static void Flush ()\n    {\n        if (BaseStream != null &amp;&amp; m_write_pos &gt; 0)\n            BaseStream.Write(m_buffer, 0, m_write_pos);\n\n        BytesWritten += m_write_pos;\n        m_write_pos = 0;\n    }\n\n    public static void WriteLine ()\n    {\n        if (m_buffer.Length - m_write_pos &lt; 1)\n            Flush();\n\n        m_buffer[m_write_pos++] = (byte)\'\\n\';\n    }\n\n    public static void WriteLinesSorted (int[] values, int count)\n    {\n        int digits = 1, max_value = 9;\n\n        for (int i = 0; i &lt; count; ++i)\n        {\n            int x = values[i];\n\n            if (m_buffer.Length - m_write_pos &lt; SPACE_RESERVE)\n                Flush();\n\n            while (x &gt; max_value)\n                if (++digits &lt; 10)\n                    max_value = max_value * 10 + 9;\n                else\n                    max_value = int.MaxValue;               \n\n            int n = x, p = m_write_pos + digits, e = p + 1;\n\n            m_buffer[p] = (byte)\'\\n\';\n\n            while (n &gt;= 10)\n            {\n                int q = n / 100, w = m_double_digit_lookup[n - q * 100];\n                n = q;\n                m_buffer[--p] = (byte)w;\n                m_buffer[--p] = (byte)(w &gt;&gt; 8);\n            }\n\n            if (n != 0 || x == 0)\n                m_buffer[--p] = (byte)((byte)\'0\' + n);\n\n            m_write_pos = e;\n        }\n    }\n}\n</code></pre>\n\n<p>That takes less than 1 ms for writing 10000 (sorted) numbers. It\'s a static class because it is intended for textual inclusion in coding challenge submissions, with a minimum of fuss and zero overhead.</p>\n\n<p>In general I found it to be <em>much</em> faster if focussed work is done on entire batches, meaning sieve a certain range, then extract all primes into a vector/array, then blast out the whole array, then sieve the next range and so on, instead of mingling everything together. Having separate functions focussed on specific tasks also makes it easier to mix and match, it enables reuse, and it eases development/testing. </p>\n'}, {'answer_id': 37176847, 'author': 'S_R', 'author_id': 4004421, 'author_profile': 'https://Stackoverflow.com/users/4004421', 'pm_score': 1, 'selected': False, 'text': '<p>Using Sieve of Eratosthenes, computation is quite faster compare to "known-wide" prime numbers algorithm.</p>\n\n<p>By using pseudocode from it\'s wiki (<a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow">https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes</a>), I be able to have the solution on C#.</p>\n\n<pre><code>/// Get non-negative prime numbers until n using Sieve of Eratosthenes.\npublic int[] GetPrimes(int n) {\n    if (n &lt;= 1) {\n        return new int[] { };\n    }\n\n    var mark = new bool[n];\n    for(var i = 2; i &lt; n; i++) {\n        mark[i] = true;\n    }\n\n    for (var i = 2; i &lt; Math.Sqrt(n); i++) {\n        if (mark[i]) {\n            for (var j = (i * i); j &lt; n; j += i) {\n                mark[j] = false;\n            }\n        }\n    }\n\n    var primes = new List&lt;int&gt;();\n    for(var i = 3; i &lt; n; i++) {\n        if (mark[i]) {\n            primes.Add(i);\n        }\n    }\n\n    return primes.ToArray();\n}\n</code></pre>\n\n<p>GetPrimes(100000000) takes 2s and 330ms.</p>\n\n<p><strong><em>NOTE</strong>: Value might vary depend on Hardware Specifications.</em></p>\n'}, {'answer_id': 38938100, 'author': 'Richard Ledbetter', 'author_id': 5739951, 'author_profile': 'https://Stackoverflow.com/users/5739951', 'pm_score': 0, 'selected': False, 'text': '<p>I have been working on find primes for about a year. This is what I found to be the fastest:</p>\n\n<pre><code>import static java.lang.Math.sqrt;\nimport java.io.PrintWriter;\nimport java.io.File;\npublic class finder {\n    public static void main(String[] args) {\n        primelist primes = new primelist();\n        primes.insert(3);\n        primes.insert(5);\n        File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");\n        file.getParentFile().mkdirs();\n        long time = System.nanoTime();\n        try{\n            PrintWriter printWriter = new PrintWriter ("file0024.txt"); \n            int linenum = 0;\n            printWriter.print("2");\n            printWriter.print (" , ");\n            printWriter.print("3");\n            printWriter.print (" , ");\n            int up;\n            int down;           \n            for(int i =1; i&lt;357913941;i++){//\n                if(linenum%10000==0){\n                    printWriter.println ("");\n                    linenum++;\n                }\n                down = i*6-1;\n                if(primes.check(down)){\n                    primes.insert(down);\n                    //System.out.println(i*6-1);\n                    printWriter.print ( down );\n                    printWriter.print (" , ");\n                    linenum++;  \n                }\n                up = i*6+1;\n                if(primes.check(up)){\n                    primes.insert(up);\n                    //System.out.println(i*6+1);\n                    printWriter.print ( up );\n                    printWriter.print (" , ");\n                    linenum++;  \n                }\n            }\n            printWriter.println ("Time to execute");\n            printWriter.println (System.nanoTime()-time);\n            //System.out.println(primes.length);\n            printWriter.close ();\n        }catch(Exception e){}\n    } \n}\nclass node{\n    node next;\n    int x;\n    public node (){\n        node next;\n        x = 3;\n    }\n    public node(int z) {\n        node next;\n        x = z;\n    }\n}\nclass primelist{\n    node first;\n    int length =0;\n    node current;\n    public void insert(int x){\n        node y = new node(x);\n        if(current == null){\n            current = y;\n            first = y;\n        }else{\n            current.next = y;\n            current = y;\n        }\n        length++;\n    }\n    public boolean check(int x){\n        int p = (int)sqrt(x);\n        node y = first;\n        for(int i = 0;i&lt;length;i++){\n            if(y.x&gt;p){\n                return true;\n            }else if(x%y.x ==0){\n                return false;\n            }\n            y = y.next;\n        }\n        return true;\n    }\n}\n</code></pre>\n\n<p>1902465190909 nano seconds to get to 2147483629 starting at 2.</p>\n'}, {'answer_id': 43820084, 'author': 'Sagar', 'author_id': 7835716, 'author_profile': 'https://Stackoverflow.com/users/7835716', 'pm_score': 1, 'selected': False, 'text': '<p>Here is my code which finds \nfirst 10,000 primes in 0.049655 sec on my laptop, first 1,000,000 primes in under 6 seconds and first 2,000,000 in 15 seconds<br>\nA little explanation. This method uses 2 techniques to find prime number</p>\n\n<ol>\n<li>first of all any non-prime number is a composite of multiples of prime numbers so this code test by dividing the test number by smaller prime numbers instead of any number, this decreases calculation by atleast 10 times for a 4 digit number and even more for a bigger number</li>\n<li>secondly besides dividing by prime, it only divides by prime numbers that are smaller or equal to the root of the number being tested further reducing the calculations greatly, this works because any number that is greater than root of the number will have a counterpart number that has to be smaller than root of the number but since we have tested all numbers smaller than the root already, Therefore we don\'t need to bother with number greater than the root of the number being tested. </li>\n</ol>\n\n<p>Sample output for first 10,000 prime number<br>\n<a href="https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0" rel="nofollow noreferrer">https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0</a> <a href="https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk" rel="nofollow noreferrer">https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk</a></p>\n\n<p>Here is the code in C language,\nEnter 1 and then 10,000 to print out the first 10,000 primes.<br>\nEdit: I forgot this contains math library ,if you are on windows or visual studio than that should be fine but on linux you must compile the code using -lm argument or the code may not work<br>\nExample: gcc -Wall -o "%e" "%f" -lm</p>\n\n<pre><code>#include &lt;stdio.h&gt;\n#include &lt;math.h&gt;\n#include &lt;time.h&gt;\n#include &lt;limits.h&gt;\n\n/* Finding prime numbers */\nint main()\n{   \n    //pre-phase\n    char d,w;\n    int l,o;\n    printf("  1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\\n"); // this question helps in setting the limits on m or n value i.e l or o \n    printf("     Enter 1 or 2 to get anwser of first or second question\\n");\n    // decision making\n    do\n    {\n        printf("  --&gt;");\n        scanf("%c",&amp;d);\n        while ((w=getchar()) != \'\\n\' &amp;&amp; w != EOF);\n        if ( d == \'1\')\n        {\n            printf("\\n  2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\\n  --&gt;");\n            scanf("%10d",&amp;l);\n            o=INT_MAX;\n            printf("  Here we go!\\n\\n");\n            break;\n        }\n        else if ( d == \'2\' )\n        {\n            printf("\\n  2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\\n  --&gt;");\n            scanf("%10d",&amp;o);\n            l=o/log(o)*1.25;\n            printf("  Here we go!\\n\\n");\n            break;\n        }\n        else printf("\\n  Try again\\n");\n    }while ( d != \'1\' || d != \'2\' );\n\n    clock_t start, end;\n    double cpu_time_used;\n    start = clock(); /* starting the clock for time keeping */\n\n    // main program starts here\n    int i,j,c,m,n; /* i ,j , c and m are all prime array \'p\' variables and n is the number that is being tested */\n    int s,x;\n\n    int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */\n    p[1]=2;\n    p[2]=3;\n    p[3]=5;\n    printf("%10dst:%10d\\n%10dnd:%10d\\n%10drd:%10d\\n",1,p[1],2,p[2],3,p[3]); // first three prime are set\n    for ( i=4;i&lt;=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */\n        p[i]=0;\n\n    n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */\n    s=sqrt(n); /* \'s\' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/\n    x=2; /* \'x\' is the biggest prime number that is smaller or equal to root of the number \'n\' being tested */\n\n    /* j ,x and c are related in this way, p[j] &lt;= prime number x &lt;= p[c] */\n\n    // the main loop begins here\n    for ( m=4,j=1,c=2; m&lt;=l &amp;&amp; n &lt;= o;)\n    /* this condition checks if all the first \'l\' numbers of primes are found or n does not exceed the set limit o */\n    {\n            // this will divide n by prime number in p[j] and tries to rule out non-primes\n            if ( n%p[j]==0 )\n            {\n                /* these steps execute if the number n is found to be non-prime */\n\n                ++n; /* this increases n by 1 and therefore sets the next number \'n\' to be tested */\n                s=sqrt(n); /* this calaulates and stores in \'s\' the new root of number \'n\' */\n                if ( p[c] &lt;= s &amp;&amp; p[c] != x ) /* \'The Magic Setting\' tests the next prime number candidate p[c] and if passed it updates the prime number x */\n                {\n                    x=p[c];\n                    ++c;\n                }\n                j=1;\n                /* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number \'n\' and also resets j to 1 for the new cycle */\n                continue; /* and this restarts the loop for the new cycle */\n            }\n            // confirmation test for the prime number candidate n\n            else if ( n%p[j]!=0 &amp;&amp; p[j]==x )\n            {\n                /* these steps execute if the number is found to be prime */\n                p[m]=n;\n                printf("%10dth:%10d\\n",m,p[m]);\n                ++n;\n                s = sqrt(n);\n                ++m;\n                j=1;\n                /* these steps stores and prints the new prime number and moves the \'m\' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */\n                continue; /* and this restarts the loop */\n                /* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/\n            }\n            ++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number \'n\' */\n            // if the cycle reaches this point that means the number \'n\' was neither divisible by p[j] nor was it a prime number\n            // and therfore it will test the same number \'n\' again in the next cycle with a bigger prime number\n    }\n    // the loops ends\n    printf("  All done !!\\n");\n    end = clock();\n    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;\n    printf("  Time taken : %lf sec\\n",cpu_time_used);\n}\n</code></pre>\n'}, {'answer_id': 48358041, 'author': 'bumblebee', 'author_id': 8552409, 'author_profile': 'https://Stackoverflow.com/users/8552409', 'pm_score': 0, 'selected': False, 'text': '<p>Here the code that I made :</p>\n\n<hr>\n\n<pre><code>enter code here\n#include &lt;cmath&gt;\n#include &lt;cstdio&gt;\n#include &lt;vector&gt;\n#include &lt;iostream&gt;\n#include &lt;algorithm&gt;\nusing namespace std;\n\n\nint main() {\n/* Enter your code here. Read input from STDIN. Print output to STDOUT*/   \n\nunsigned long int n;\n\nint prime(unsigned long int);\n\nscanf("%ld",&amp;n);\n\nunsigned long int val;\n\nfor(unsigned long int i=0;i&lt;n;i++)\n{\n    int flag=0;\n\n    scanf("%ld",&amp;val);\n\n    flag=prime(val);\n\n    if(flag==1)\n        printf("yes\\n");\n\n    else\n        printf("no\\n");\n}\n\nreturn 0;\n\n}\n\nint prime(unsigned long int n)\n{\n\nif(n==2) return 1;\n\nelse if (n == 1||n%2==0)  return 0;\n\nfor (unsigned long int i=3; i&lt;=sqrt(n); i+=2)\n    if (n%i == 0)\n        return 0;\n\nreturn 1;\n}\n</code></pre>\n'}, {'answer_id': 50778831, 'author': 'Flavio', 'author_id': 3310801, 'author_profile': 'https://Stackoverflow.com/users/3310801', 'pm_score': 0, 'selected': False, 'text': "<p>Using the Array.prototype.find() method in Javascript. 2214.486 ms</p>\n\n<pre><code>function isPrime (number) {\n\n  function prime(element) {\n    let start = 2;\n    while (start &lt;= Math.sqrt(element)) {\n      if (element % start++ &lt; 1) {\n        return false;\n      }\n    }\n    return element &gt; 1;\n  }\n\n  return [number].find(prime)\n\n}\n\nfunction logPrimes (n) {\n\n  let count = 0\n  let nth = n\n\n  let i = 0\n  while (count &lt; nth) {\n    if (isPrime(i)) {\n      count++\n      console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms\n      if (count === nth) {\n        console.log('while i', i)\n        console.log('count', count)\n      }\n    }\n    i++\n  }\n\n}\n\nconsole.time(logPrimes)\n\nlogPrimes(10000)\n\nconsole.timeEnd(logPrimes) // 2214.486ms\n</code></pre>\n"}, {'answer_id': 51583803, 'author': 'MubashirEbad', 'author_id': 2581549, 'author_profile': 'https://Stackoverflow.com/users/2581549', 'pm_score': 0, 'selected': False, 'text': '<p>I can give you some tips, you have to implement it.</p>\n\n<ol>\n<li>For each number, get the half of that number. E.g. for checking 21, only obtain the remainder by dividing it from range 2-10.</li>\n<li>If its an odd number, only divide by odd number, and vice versa. Such as for 21, divide with 3, 5, 7, 9 only.</li>\n</ol>\n\n<p>Most efficient method I got up to so far.</p>\n'}, {'answer_id': 53332013, 'author': 'itsjwala', 'author_id': 9485283, 'author_profile': 'https://Stackoverflow.com/users/9485283', 'pm_score': 0, 'selected': False, 'text': "<p>Since you want first 10000 primes only, rather than coding complex algorithm I'll suggest \nthe following</p>\n\n<pre><code>boolean isPrime(int n){\n//even but is prime\n    if(n==2)\n        return true;\n//even numbers filtered already \n    if(n==0 || n==1 || n%2==0)\n        return false;\n\n// loop for checking only odd factors\n// i*i &lt;= n  (same as i&lt;=sqrt(n), avoiding floating point calculations)\n    for(int i=3 ; i*i &lt;=n ; i+=2){\n    // if any odd factor divides n then its not a prime!\n        if(n%i==0)\n            return false;\n    }\n// its prime now\n    return true;\n}\n</code></pre>\n\n<p>now call is prime as you need it <br></p>\n\n<pre><code>for(int i=1 ; i&lt;=1000 ; i++){\n    if(isPrime(i)){\n       //do something\n    }\n}\n</code></pre>\n"}, {'answer_id': 58829625, 'author': 'Steven Armstrong', 'author_id': 1946543, 'author_profile': 'https://Stackoverflow.com/users/1946543', 'pm_score': 0, 'selected': False, 'text': "<p>This is an old question, but there's something here everyone's missing...</p>\n\n<p>For primes this small, trial division isn't <em>that</em> slow... there are only 25 primes under 100. With so few primes to test, and such small primes, we can pull out a neat trick!</p>\n\n<p>If a is coprime to b, then gcd a b = 1. Coprime. Fun word. Means it doesn't share <em>any prime factors</em>. We can thus test for divisibility by several primes with one GCD call. How many? Well, the product of the first 15 primes is less than 2^64. And the product of the next 10 is also less than 2^64. That's all 25 that we need. But is it worth it?</p>\n\n<p>Let's see:</p>\n\n<pre><code>check x = null $ filter ((==0) . (x `mod`)) $ [&lt;primes up to 101&gt;]\nPrelude&gt; length $ filter check [101,103..85600]\n&gt;&gt;&gt; 9975\n(0.30 secs, 125,865,152 bytes\n\na = 16294579238595022365 :: Word64\nb = 14290787196698157718\npre = [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]\nprimes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) [99,101..85600]\nmain = print $ length primes\n\nPrelude&gt; main\n&gt;&gt;&gt; 10000\n(0.05 secs, 36,387,520 bytes)\n</code></pre>\n\n<p>A 6 fold improvement there.</p>\n\n<p>(<code>length</code> is to force the list to be computed. By default Haskell prints things 1 Unicode character at a time and so actually <em>printing</em> the list will either dominate the time or dominate the amount of actual code used.)</p>\n\n<p>Of course, this is running in GHCi - a repl running interpreted code - on an old laptop and it is not interpreting any of these numbers as <code>int64</code>s or even <code>BigInt</code>s, nor will it even if you ask it to (well, you <em>can</em> force it, but it's ugly and doesn't really help). It is interpreting every single number there as generalized <em>Integer-like</em> things that can be specialized to some particular type via dictionary lookup, and it is traversing a linked list (which is not fused away here as it's not compiled) 3 times. Interestingly, hand fusing the two filters actually slows it down in the REPL. </p>\n\n<p>Let's compile it:</p>\n\n<pre><code>...\\Haskell\\8.6\\Testbed&gt;Primes.exe +RTS -s\n10000\n606,280 bytes allocated in the heap\nTotal   time    0.000s  (  0.004s elapsed)\n</code></pre>\n\n<p>Using the RTS report because Windows. Some lines trimmed because they aren't relevant - they were other GC data, or measurements of only part of the execution, and together add up to 0.004s (or less). It's also not constant folding, because Haskell doesn't actually do much of that. If we constant fold ourselves (<code>main = print 10000</code>), we get dramatically lower allocation:</p>\n\n<pre><code>...Haskell\\8.6\\Testbed&gt;Primes.exe +RTS -s\n10000\n47,688 bytes allocated in the heap\nTotal   time    0.000s  (  0.001s elapsed)\n</code></pre>\n\n<p>Literally just enough to load the runtime, then discover there's nothing to do but print a number and exit. Let's add wheel factorization:</p>\n\n<pre><code>wheel = scanl (+) 7 $ cycle [4, 2, 4, 2, 4, 6, 2, 6]\nprimes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) $ takeWhile (&lt;85600) wheel\n\nTotal   time    0.000s  (  0.003s elapsed)\n</code></pre>\n\n<p>Cut down approximately 1/3rd relative to our reference of <code>main = print 10000</code>, but there's definitely room for more optimization. It actually stopped to perform a GC in there for example, while with tweaking there shouldn't be any heap use. For some reason, compiling for profiling here actually cuts the runtime down to 2 milliseconds:</p>\n\n<pre><code>Tue Nov 12 21:13 2019 Time and Allocation Profiling Report  (Final)\n\n   Primes.exe +RTS -p -RTS\n\ntotal time  =        0.00 secs   (2 ticks @ 1000 us, 1 processor)\ntotal alloc =     967,120 bytes  (excludes profiling overheads)\n</code></pre>\n\n<p>I'm going to leave this as is for now, I'm pretty sure random jitter is starting to dominate.</p>\n"}, {'answer_id': 61831666, 'author': 'mohamad eldimardash', 'author_id': 9234603, 'author_profile': 'https://Stackoverflow.com/users/9234603', 'pm_score': 0, 'selected': False, 'text': '<pre><code>def compute_primes(bound):\n"""\nReturn a list of the prime numbers in range(2, bound)\nImplement the Sieve of Eratosthenes\nhttps://en.wikipedia.org/wiki/Sieve_of_Eratosthenes\n"""\nprimeNumber = [True for i in range(bound + 1)]\nstart_prime_number = 2\nprimes = []\nwhile start_prime_number * start_prime_number &lt;=bound:\n    # If primeNumber[start_prime_number] is not changed, then it is a prime\n    if primeNumber[start_prime_number]:\n        # Update all multiples of start_prime_number\n        for i in range(start_prime_number * start_prime_number, bound + 1, start_prime_number):\n            primeNumber[i] = False\n    start_prime_number += 1\n\n# Print all prime numbers\nfor start_prime_number in range(2, bound + 1):\n    if primeNumber[start_prime_number]:\n        primes.append(start_prime_number)\n\nreturn primes\n</code></pre>\n\n<p>print(len(compute_primes(200)))</p>\n\n<p>print(len(compute_primes(2000)))</p>\n'}, {'answer_id': 74401260, 'author': '1729-Shivam-Maurya', 'author_id': 19608147, 'author_profile': 'https://Stackoverflow.com/users/19608147', 'pm_score': 0, 'selected': False, 'text': '<p>This is a Python code that prints prime numbers between 1 to 1000000.</p>\n<pre class="lang-py prettyprint-override"><code>import math\n \nk=0\n\nfactor=0\n\npl=[]\n\nfor i in range(1,1000000):\n\n    k=int(math.sqrt(i))\n    if i==2 or i==3:\n        pl.append(i)\n    for j in range(2,k+1):\n        if i%j==0:\n            factor=factor+1\n        elif factor==0 and j==k:\n            pl.append(i)\n    factor=0\n\nprint(pl)  \nprint(len(pl))\n</code></pre>\n'}]
['https://Stackoverflow.com/questions/622', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/184/']