Return the first N primes

Question

With a twist; your algorithm has to be less complex than O(X²) 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++; }

Answer 1

J, 4 characters

p:i.

Usage:

   p:i.10
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)

Answer 2

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.

i,j,m,*p;
f(n){
    p=calloc(m=n*24,4);
    for(i=2;n;i++)
        if(!p[i])for(n--,printf("%d\n",j=i);p[j+=i]=j<m;);
}

Answer 3

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
1.8597116027280054
Prelude> logBase (7/5) (3.31/1.60)        -- in N
2.1604889825177507

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

Answer 4

Ruby 37

require 'prime'
p Prime.take gets.to_i

Answer 5

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
for(i<-List.range(3,M)
if(p(i))){
var j=2*i;
while(j<M){
if(p(j))p(j)=false
j+=i}
}
(1 to M).filter(x=>p(x))
}
println(c(args(0).toInt))
}

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}
do
  /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).

Answer 6

Perl: 249 chars

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

sub p{
  $n=shift;
  $m=$n-1;
  return$n==2||$n==3if$n<=3or!($n&1);
  $s=unpack"%32b*",pack"L",($m&-$m)-1;
  for(1..5){
    next if($x=(int(rand($n-3))+2)**($n>>$s)%$n)==1||$x==$m;
    map{($x=$x**2%$n)==1&&last;$x==$m&&next}(1..$s-1);
  0}
1}
p($_)&&print"$_\n"for(1..$ARGV[0]);

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

Answer 7

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:

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
}