# 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. – GigaWatt 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. – Bunnit 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?:-) – Artem Ice Aug 10 '12 at 7:55
I mean the J source code... – Artem Ice Aug 10 '12 at 9:40

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

-

``````p=2:[i|i<-[3..],all((>0).mod i)\$takeWhile((<=i).(^2))p]
``````

This is a list of all primes; taking `n` of those, like

``````GHCi> take 9 p
[2,3,5,7,11,13,17,19,23]
``````

has the same complexity as in your example. (It's actually the same algorithm, "surprisingly"...)

In case you insist, we can also build the `take n` in as a function argument:

``````p n=take n\$2:[i|i<-[3..],all((>0).mod i).takeWhile((<=i).(^2))\$p n]
``````
-
 your 2nd code is very slow in GHCi, non-compiled. :) (no sharing...). Its empirical complexity is `n^1.7 .. 1.8`. When `-O2` compiled it runs fast, under `n^1.4`. I don't know what the rules about compilation are here. `q n=let p=(...)in take n p` is 74 chars, runs under `n^1.4` non-compiled, as well as the 1st variant. (`n` means, n primes produced). – Will Ness Aug 8 '12 at 18:38 Sure it's slow if you evaluate it interpreted. And that worse complexity is obviously due to lack of memoisation of `p n`. But as it's still below O (n ²) it's ok, isn't it? This is code golf after all... – leftaroundabout Aug 9 '12 at 11:30 yes, it is below n^2. :) – Will Ness Aug 9 '12 at 12:13

PYTHON

Just for fun:

``````import urllib2, collections
def primos(tamanho):
f = urllib2.urlopen('http://primes.utm.edu/lists/small/10000.txt')
for line in f:
line = collections.deque(line.split())
while line:
if not tamanho:
return
tamanho -= 1
yield line.popleft()

for primo in primos(9):
print primo
``````
-
 Can you elaborate on the Big-O of your approach? – user unknown Mar 15 '12 at 3:28

# 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

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

-
 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

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

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

-

# Mathematica 13 chars

The following returns the first n primes:

``````Prime@Range@n
``````

Timings for 10, 100, 1000, ... 10000000 primes

``````t = Table[Timing[Prime@Range@(10^k);][[1]], {k, 7}]
ListLogPlot[t, AxesLabel -> {"Power of 10", "Occurences"}]
``````

I'm fairly certain that Mathematica uses different methods of finding primes at different intervals so it's a little like comparing apples and oranges, but the logplot looks kind of flat. Can someone explain what this signifies as regards Big-O?

-

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