With a twist; your algorithm has to be less complex than O(X2) where X is the Nth prime. Your solution post should include the character count and the theoretical complexity in terms of X (or N, which ~= X/ln(X) and so will usually be more efficient)

Here's a hint solution in C# (O(Xln(sqrt(X))), 137 chars):

public List<int> P(int n){var r = new List<int>{2}; int i=3; while(r.Count<n) if(!r.TakeWhile(x=>x<Math.Sqrt(i)).Any(x=>i%x==0)) r.Add(i++); else i++; }

  • 2
    \$\begingroup\$ I fail to see how the sample is O(n*ln(sqrt(n))). O(n*sqrt(n)) maybe, but there's nothing hints to why it would have an ln in there. Please correct me if I'm wrong. \$\endgroup\$
    – Mr. Llama
    Commented Mar 8, 2012 at 23:07
  • \$\begingroup\$ For each value tested, it's checked against all prime numbers less than the square root of the number. If you haven't found a prime factor by then you won't find one. There are on the order of ln(i) primes between 0 and any i. So, in finding prime X which is the Nth prime, you will have run checks equal to ln(sqrt(X)) against each number up to and including X. Or, simply, O(X*ln(sqrt(X))). \$\endgroup\$
    – KeithS
    Commented Mar 8, 2012 at 23:41
  • \$\begingroup\$ By the way, O(ln(sqrt(x)) == O(ln(x)) \$\endgroup\$ Commented Mar 11, 2012 at 4:48
  • \$\begingroup\$ @KeithS actully, π(i) ~ i/ln(i). So, sqrt(X)/ln(sqrt(X)) ~ sqrt(X)/ln(X) and overall complexity of producing N ~= X/ln(X) primes is O(X^1.5 / (ln(X))^2 ), not counting the testing of composites, most of which are multiples of 2 or 3, so will be weeded out with very few tests. \$\endgroup\$
    – Will Ness
    Commented Aug 8, 2012 at 18:04
  • \$\begingroup\$ @KeithS or in terms of N: X ~= N*log(N), it is O(N^1.5/sqrt(ln(N))). Or in practical terms N^1.4 .. 1.45. So you might want to amend your spec to "below N^1.5" (or at least "below X^1.5") or all kinds of solutions will have to be admitted. \$\endgroup\$
    – Will Ness
    Commented Aug 9, 2012 at 12:36

7 Answers 7


J, 4 characters



2 3 5 7 11 13 17 19 23 29

The problem with using J here is that I don't really know how efficient it is. I'd assume that as a language specialising in "mathematical, statistical, and logical analysis of data", that the algorithm used to generate the primes is pretty good.

I did look at the C source for clues, but it turns out that the C source for J is almost as unreadable as J itself. :-)

(The file is called v2.c for anyone who wants to have a look)

  • 1
    \$\begingroup\$ Haha, that C code is crazy, looks like someone tried to codegolf it. \$\endgroup\$ Commented Mar 9, 2012 at 17:54
  • \$\begingroup\$ My lord! The source looks as if it has been compiled already. \$\endgroup\$
    – MrZander
    Commented Mar 11, 2012 at 21:01
  • \$\begingroup\$ You could do some timing, like I did, couldn't you? \$\endgroup\$ Commented Mar 15, 2012 at 3:28
  • \$\begingroup\$ My goodness, is it how thinking in J affects one's coding style?:-) \$\endgroup\$
    – defhlt
    Commented Aug 10, 2012 at 7:55
  • \$\begingroup\$ I mean the J source code... \$\endgroup\$
    – defhlt
    Commented Aug 10, 2012 at 9:40

C, 98 characters

The good old sieve method.
We assume the first N primes are among the first N*24 integers. this works up to 2^32, because ln(2^32)<24. A general solution would need to estimate prime density, but since I use 32bit integers, I saw no need to generalize.
Complexity analysis (which I may do later) should use a formula instead of the constant 24.

  • \$\begingroup\$ Nice work, very nice. Note: The expression p[j+=i]=j<m walks off the end of the array and corrupts memory. On my system, it corrupts printf and produces '\0' characters in the output (visible with | less or with | hexdump -C). To fix, instead say p[j]=j<m,j+=i, or maybe there is a way to write it with while(j<m)p[j]=1,j+=i; ? \$\endgroup\$ Commented Jul 28, 2014 at 4:19
  • \$\begingroup\$ @ToddLehman, you're right, I'm writing out of bounds. The easy fix is changing calloc's 2nd parameter to 8. I can't seem to do it, because of my employer's upload policy. \$\endgroup\$
    – ugoren
    Commented Jul 28, 2014 at 12:17

Haskell, 47 46

Since the problem definition demands less than O(X^2) complexity, where X ~= N*log(N), the following solution is acceptable. Its theoretical complexity is below O(X^2), testing each number below X by all its preceding numbers until a divisor is found. For primes only, having ~ X/log(X) primes overall, the complexity is thus O(X^2/log(X)). Most of the composites are multiples of small primes so are only divided few times, so they don't count.

p n=take n[n|n<-[2..],all((>0).rem n)[2..n-1]]

Prelude> last $ p 500
3571    (1.60 secs)
Prelude> last $ p 700
5279    (3.31 secs)
Prelude> logBase (5279/3571) (3.31/1.60)  -- in X
Prelude> logBase (7/5) (3.31/1.60)        -- in N

Prelude> last $ p 900
6997    (5.69 secs)
Prelude> logBase (6997/5279) (5.69/3.31)
1.9228821930296973                        -- in X
Prelude> logBase (9/7) (5.69/3.31)
2.155714108637307                         -- in N

If the complexity constraint in the problem definition will be amended to below O(N^1.5) (as I believe it should) then this solution will not be acceptable. That is why I post it in addition to another Haskell solution which is indeed better than O(N^1.5).


Ruby 37

require 'prime'
p Prime.take gets.to_i
  • \$\begingroup\$ Can you elaborate on the Big-O of your approach? \$\endgroup\$ Commented Mar 15, 2012 at 3:29

scala 191

Not the shortest one...

object P extends App{
def c(M:Int)={
val p=(false::false::true::List.range(3,M+1).map(_%2!=0)).toArray
var j=2*i;
(1 to M).filter(x=>p(x))

Just measuring the method c, like the others do.

But how to prove, that it fulfills the Big-O requierement?

Well, I feed it with numbers, each twice as big as the number before. If it was of O(x²) complexity, it should need about 4 times as long, shouldn't it?

So I just measure it:

for p in {10..22}
  /usr/bin/time scala P $((2**p))> /dev/null
  echo "N="$((2**p))
done 2>&1 | tee primes.log 

and then it's just a grep:

egrep -o "(^.*user|N=.*|#)" primes.log | tr "\n" "\t" | tr "#" "\n"
0.57user    N=1024  
0.54user    N=2048  
0.56user    N=4096  
0.59user    N=8192  
0.62user    N=16384 
0.66user    N=32768 
0.70user    N=65536 
0.77user    N=131072    
0.99user    N=262144    
1.48user    N=524288    
2.59user    N=1048576   
5.68user    N=2097152   
10.79user   N=4194304   

So in the beginning there is only a startup overhead of about .55s - later it is a linear growth. For N'=2*N, t(N') ≈ 2*t(N).

  • \$\begingroup\$ you can assume growth of the order n^a, and estimate a as log( t2/t1 ) / log( n2/n1 ). Optimal trial division should run at about ~ n^1.30 .. 1.45. Sieve of Eratosthenes can be n^1.0 .. 1.1. A priority-queue based s. of E. runs at about n^1.2 (it has an additional log factor compared with SoE). \$\endgroup\$
    – Will Ness
    Commented Aug 8, 2012 at 18:35

Perl: 249 chars

The sieve certainly would have been shorter, but here is an implementation of the Miller-Rabin test:

sub p{
    next if($x=(int(rand($n-3))+2)**($n>>$s)%$n)==1||$x==$m;

Wikipedia says the runtime is O((log(X))^3)


Ruby (91)

Almost same as the example, so should have similar complexity. Unless I'm still missing something obvious (almost used select instead of take_while to save a few chars)

q=->n{k=[2];p=3;while k.size<n;k<<p if !k.take_while{|x|x*x<=p}.any?{|x|p%x<1};p+=2;end;k}

and with some whitespace:

  while k.size<n;
    k<<p if !k.take_while{|x| x*x <= p }.any?{|x| p%x < 1};

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.