# Return the first N primes

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++; }

• 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. – Mr. Llama Mar 8 '12 at 23:07
• 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))). – KeithS Mar 8 '12 at 23:41
• By the way, O(ln(sqrt(x)) == O(ln(x)) – Keith Randall Mar 11 '12 at 4:48
• @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. – Will Ness Aug 8 '12 at 18:04
• @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. – Will Ness Aug 9 '12 at 12:36

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

• Haha, that C code is crazy, looks like someone tried to codegolf it. – Scott Logan Mar 9 '12 at 17:54
• My lord! The source looks as if it has been compiled already. – MrZander Mar 11 '12 at 21:01
• You could do some timing, like I did, couldn't you? – user unknown Mar 15 '12 at 3:28
• My goodness, is it how thinking in J affects one's coding style?:-) – defhlt Aug 10 '12 at 7:55
• I mean the J source code... – defhlt Aug 10 '12 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.

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;);
}

• 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; ? – Todd Lehman Jul 28 '14 at 4:19
• @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. – ugoren Jul 28 '14 at 12:17

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

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). • 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). – Will Ness Aug 8 '12 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{$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)

# 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
}


# Ruby 37

require 'prime'
p Prime.take gets.to_i

• Can you elaborate on the Big-O of your approach? – user unknown Mar 15 '12 at 3:29