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

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

The Sieve of Atkin is probably what you're looking for, its upper bound running time is O(N/log log N).

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. Resource for my statement

I recommend a sieve, either the Sieve of Eratosthenes or the Sieve of Atkin.

The sieve or Eratosthenes is probably the most intuitive method of finding a list of primes. Basically you:

Obviously there are quite a few optimizations that can be done to make this algorithm work faster, but this is the basic idea.

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

Sieve of Eratosthenes Source Code: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Sieve of Atkin Source Code: http://cr.yp.to/primegen.html

This isn't strictly against the hardcoding restriction, but comes terribly close. Why not programatically download this list and print it out, instead?

http://primes.utm.edu/lists/small/10000.txt

GateKiller, how about adding a

`break`

to that`if`

in the`foreach`

loop? That would speed up thingsa lotbecause 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 :-) ...)In Haskell, we can write down almost word for word the mathematical definition of the sieve of Eratosthenes, "

primes are natural numbers above 1 without any composite numbers, where composites are found by enumeration of each prime's multiples":`primes !! 10000`

is near-instantaneous.References:

_{The above code is easily tweaked into working on odds only, primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)). Time complexity is much improved (to just about a log factor above optimal) by folding in a tree-like structure, and space complexity is drastically improved by multistage primes production, in}_{(In Haskell the parentheses are used for grouping, a function call is signified just by juxtaposition, (:) is a cons operator for lists, and (.) is a functional composition operator: (f . g) x = (\y -> f (g y)) x = f (g x)).}@Matt: log(log(10000)) is ~2

From the wikipedia article (which you cited) Sieve of Atkin:

Given asymptotic computational complexities along

`O(N)`

(for Eratosthenes) and`O(N/log(log(N)))`

(for Atkin) we can't say (for small`N=10_000`

) which algorithm if implemented will be faster.Achim Flammenkamp wrote in The Sieve of Eratosthenes:

cited by:

@num1

Therefore for

`10_000`

Sieve of Eratosthenes can be faster then Sieve of Atkin.To answer OP the code is prime_sieve.c (cited by

`num1`

)Using GMP, one could write the following:

On my 2.33GHz Macbook Pro, it executes as follows:

Calculating 1,000,000 primes on the same laptop:

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.

Not efficient at all, but you can use a regular expression to test for prime numbers.

This tests if, for a string consisting of

k“`1`

”s,kisnot prime(i.e. whether the string consists of one “`1`

” or any number of “`1`

”s that can be expressed as ann-ary product).I have adapted code found on the CodeProject to create the following:

Testing this on my ASP.NET Server took the rountine about 1 minute to run.

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.

Sieve of Eratosthenes is the way to go, because of it's simplicity and speed. My implementation in C

CPU Time to find primes (on Pentium Dual Core E2140 1.6 GHz, using single core)

Adapting and following on from GateKiller, here's the final version that I've used.

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)

The Sieve seems to be the wrong answer. The sieve gives you the primes

up toa numberN, not thefirst Nprimes. Run @Imran or @Andrew Szeto, and you get the primes up to N.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.

In Python

The deque sieve algorithm mentioned by BenGoldberg 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).

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.

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.

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#).

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++.

(Sidenote: I'm using the free LINQPad 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).C# doesn't have an explicit deque type but the plain

`List<int>`

works well enough for demonstrating the algorithm.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.

Here are the two helper functions:

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.

`sieve[0]`

) has already been sieved when we get to it, because it got run over while it was part of the overflow area.The number that is represented by

`sieve[0]`

is held in`sieve_base`

, although`sieve_front`

or`window_base`

would also be a good names that allow to draw parallels to Ben's code or implementations of segmented/windowed sieves.If

`sieve[0]`

contains a non-zero value then that value is a factor of`sieve_base`

, 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`sieve[0]`

, its current working offset is 0.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

`sieve[0]`

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`sieve_base == current_prime_squared`

(which implies`sieve[0] == 0`

, by the way).Now the case

`sieve[0] == 0 && sieve_base < current_prime_squared`

is easily explained: it means that`sieve_base`

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.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.

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

`int`

for`ushort`

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#).

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).

Note: the C# code uses

`int`

instead of`uint`

because newer compilers have a habit of generating substandard code for`uint`

, probably in order to push people towards signed integers... In the C++ version of the code above I used`unsigned`

throughout, naturally; the benchmark had to be in C++ because I wanted it be based on a supposedly adequate deque type (`std::deque<unsigned>`

; there was no performance gain from using`unsigned short`

). Here are the numbers for my Haswell laptop (VC++ 2015/x64):Note: the C# times are pretty much exactly double the C++ timings, which is pretty good for C# and ìt shows that

`List<int>`

is no slouch even if abused as a deque.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.

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 Find prime positioned prime number 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...

To put things a bit into perspective, here are the C++ timings for sieving up to 100,000,000:

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).

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.

Also, many of the timings reported by other respondents in this topic are probably dominated by

output time. That's an entirely different war, where my main weapon is a simple class like this: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.

In general I found it to be

muchfaster 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.Here is my VB 2008 code, which finds all primes <10,000,000 in 1 min 27 secs on my work laptop. It skips even numbers and only looks for primes that are < the sqrt of the test number. It is only designed to find primes from 0 to a sentinal value.

The following Mathcad code calculated the first million primes in under 3 minutes.

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.

Here is a C++ solution, using a form of SoE:

Note that this version of the Sieve can compute primes indefinitely.

Also note, the STL

`deque`

takes`O(1)`

time to perform`push_back`

,`pop_front`

, and random access though subscripting.The

`resize`

operation takes`O(n)`

time, where`n`

is the number of elements being added. Due to how we are using this function, we can treat this is a small constant.The body of the

`while`

loop in`my_insert`

is executed`O(log log n)`

times, where`n`

equals the variable`maybe_prime`

. This is because the condition expression of the`while`

will evaluate to true once for each prime factor of`maybe_prime`

. See "Divisor function" on Wikipedia.Multiplying by the number of times

`my_insert`

is called, shows that it should take`O(n log log n)`

time to list`n`

primes... which is, unsurprisingly, the time complexity which the Sieve of Eratosthenes is supposed to have.However, while this code

isefficient, it's not themost efficient... I would strongly suggest using a specialized library for primes generation, such as primesieve. Any truly efficient, well optimized solution, will take more code than anyone wants to type into Stackoverflow.Using Sieve of Eratosthenes, computation is quite faster compare to "known-wide" prime numbers algorithm.

By using pseudocode from it's wiki (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), I be able to have the solution on C#.

GetPrimes(100000000) takes 2s and 330ms.

NOTE: Value might vary depend on Hardware Specifications.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

`calcPrimes()`

. The primes are stored in an array called Primzahlen. I recommend a 64bit CPU because the calculations are with 64bit integers.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 http://primes.utm.edu/lists/small/10000.txt. To check if

`n`

is prime or not, divide`n`

by the numbers from`2`

to`sqrt(n)`

. If any of this range of number perfectly divides`n`

then it's not prime.I have been working on find primes for about a year. This is what I found to be the fastest:

1902465190909 nano seconds to get to 2147483629 starting at 2.

Here is my code which finds first 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

A little explanation. This method uses 2 techniques to find prime number

Sample output for first 10,000 prime number

https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

Here is the code in C language, Enter 1 and then 10,000 to print out the first 10,000 primes.

Edit: 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

Example: gcc -Wall -o "%e" "%f" -lm

Here the code that I made :

Using the Array.prototype.find() method in Javascript. 2214.486 ms

I can give you some tips, you have to implement it.

Most efficient method I got up to so far.

Since you want first 10000 primes only, rather than coding complex algorithm I'll suggest the following

now call is prime as you need it