List of first n prime numbers most efficiently and in shortest code [closed]

Question

Rules are simple:

• First n primes (not primes below n), should be printed to standard output separated by newlines (primes should be generated within the code)
• primes cannot be generated by an inbuilt function or through a library, i.e. use of a inbuilt or library function such as, prime = get_nth_prime(n), is_a_prime(number), or factorlist = list_all_factors(number) won't be very creative.

• Scoring - Say, we define Score = f([number of chars in the code]), O(f(n)) being the complexity of your algorithm where n is the number of primes it finds. So for example, if you have a 300 char code with O(n^2) complexity, score is 300^2 = 90000, for 300 chars with O(n*ln(n)), score becomes 300*5.7 = 1711.13 (let's assume all logs to be natural logs for simplicity)

• Use any existing programming language, lowest score wins

Edit: Problem has been changed from finding 'first 1000000 primes' to 'first n primes' because of a confusion about what 'n' in O(f(n)) is, n is the number of primes you find (finding primes is the problem here and so complexity of the problem depends on the number of primes found)

Note: to clarify some confusions on complexity, if 'n' is the number of primes you find and 'N' is the nth prime found, complexity in terms of n is and N are not equivalent i.e. O(f(n)) != O(f(N)) as , f(N) != constant * f(n) and N != constant * n, because we know that nth prime function is not linear, I though since we were finding 'n' primes complexity should be easily expressible in terms of 'n'.

As pointed out by Kibbee, you can visit this site to verify your solutions (here, is the old google docs list)

Please Include these in your solution -

• what complexity your program has (include basic analysis if not trivial)

• character length of code

• the final calculated score

This is my first CodeGolf Question so, if there is a mistake or loophole in above rules please do point them out.

Answer 1

Python (129 chars, O(n*log log n), score of 203.948)

I'd say the Sieve of Eratosthenes is the way to go. Very simple and relatively fast.

N=15485864
a=[1]*N
x=xrange
for i in x(2,3936):
 if a[i]:
  for j in x(i*i,N,i):a[j]=0
print [i for i in x(len(a))if a[i]==1][2:]

Improved code from before.

Python (191 156 152 chars, O(n*log log n)(?), score of 252.620(?))

I cannot at all calculate complexity, this is the best approximation I can give.

from math import log as l
n=input()
N=n*int(l(n)+l(l(n)))
a=range(2,N)
for i in range(int(n**.5)+1):
 a=filter(lambda x:x%a[i] or x==a[i],a)
print a[:n]

n*int(l(n)+l(l(n))) is the top boundary of the nth prime number.

Answer 2

Haskell, n^1.1 empirical growth rate, 89 chars, score 139 (?)

The following works at GHCi prompt when the general library that it uses have been previously loaded. Print n-th prime, 1-based:

let s=3:minus[5,7..](unionAll[[p*p,p*p+2*p..]|p<-s])in getLine>>=(print.((0:2:s)!!).read)

This is unbounded sieve of Eratosthenes, using a general-use library for ordered lists. Empirical complexity between 100,000 and 200,000 primes O(n^1.1). Fits to O(n*log(n)*log(log n)).

About complexity estimation

I measured run time for 100k and 200k primes, then calculated logBase 2 (t2/t1), which produced n^1.09. Defining g n = n*log n*log(log n), calculating logBase 2 (g 200000 / g 100000) gives n^1.12.

Then, 89**1.1 = 139, although g(89) = 600.       --- (?)

It seems that for scoring the estimated growth rate should be used instead of complexity function itself. For example, g2 n = n*((log n)**2)*log(log n) is much better than n**1.5, but for 100 chars the two produce score of 3239 and 1000, respectively. This can't be right. Estimation on 200k/100k range gives logBase 2 (g2 200000 / g2 100000) = 1.2 and thus score of 100**1.2 = 251.

Also, I don't attempt to print out all primes, just the n-th prime instead.

No imports, 240 chars. n^1.15 empirical growth rate, score 546.

main=getLine>>=(print.s.read)
s n=let s=3:g 5(a[[p*p,p*p+2*p..]|p<-s])in(0:2:s)!!n
a((x:s):t)=x:u s(a$p t)
p((x:s):r:t)=(x:u s r):p t
g k s@(x:t)|k<x=k:g(k+2)s|True=g(k+2)t
u a@(x:r)b@(y:t)=case(compare x y)of LT->x:u r b;EQ->x:u r t;GT->y:u a t

Answer 3

This is so easy even my text editor can do this!

Vim: 143 keystrokes (115 actions): O(n^2*log(n)): Score: 101485.21

Submission:

qpqqdqA^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"ddmpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0qqpmp"aywgg@dqgg@p

Input: N should be on the first line of a blank document. After this is finished, each prime from 2 to N will be a separate line.

Running the Commands:

First, note that any commands with a caret in front of them mean you need to hold Ctrl and type the next letter (e.g. ^V is Ctrl-v and ^R is Ctrl-r).

This will overwrite anything in your @a, @b, @d, and @p registers.

Because this uses q commands, it can't just be placed in a macro. However, here are some tips for running it.

• qpqqdq just clears registers
• A^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"dd will create a list of numbers 2 to N+1. This is a break between the two main parts, so once this is done, you shouldn't need to do it again
• mpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0qqpmp"aywgg@dqgg@p does need to be typed in one go. Try to avoid backspace as it may screw something up.
  • If you make a mistake, type qdqqpq then try this line again.

For large N, this is very slow. It took around 27 minutes to run N=5000; consider yourself warned.

Algorithm:

This uses a basic recursive algorithm for finding primes. Given a list of all primes between 1 and A, A+1 is prime if it not divisible by any of the numbers in the list of primes. Start at A = 2 and add primes to the list as they are found. After N recursions, the list will contain all the primes up to N.

Complexity

This algorithm has a complexity of O(nN), where N is the input number and n is the number of primes up to N. Each recursion tests n numbers, and N recursions are performed, giving O(nN).

However, N ~ n*log(n), giving the final complexity as O(n²*log(n))(https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number)

Explanation

It's not easy to discern the program flow from the vim commands, so I rewrote it in Python following the same flow. Like the Vim code, the python code will error out when it reaches the end. Python doesn't like too much recursion; if you try this code with N > 150 or so, it will reach the max recursion depth

N = 20
primes = range(2, N+1)

# Python needs these defined.
mark_p = b = a = -1

# Check new number for factors. 
# This macro could be wrapped up in @d, but it saves space to leave it separate.
def p():
    global mark_d, mark_p, primes, a
    mark_d = 0
    print(primes)
    a = primes[mark_p]
    d()      

# Checks factor and determine what to do next
def d():
    global mark_d, mark_p, a, b, primes
    b = primes[mark_d]
    if(a == b): # Number is prime, check the next number
        mark_p += 1
        p()
    else:
        if(a%b == 0): # Number is not prime, delete it and check next number
            del(primes[mark_p])
            p()
        else: # Number might be prime, try next possible factor
            mark_d += 1
            d()

mark_p = 0 #Start at first number         
p()

Now, to break down the actual keystrokes!

• qpqqdq Clears out the @d and @p registers. This will ensure nothing runs when setting up these recursive macros.

• A^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"dd Turns the input into a list of numbers from 2 to N+1. The N+1 entry is deleted as a side effect of setting up the @d macro.

  • Specifically, writes a macro that increments a number, then copies it on the next line, then it writes a 1 and executes this macro N times.

• mpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0q writes the @d macro, which implements the d() function above. "If" statements are interesting to implement in Vim. By using the search operator *, it's possible to choose a certain path to follow. Breaking the command down further we get

  • mpqd Set the p mark here and start recording the @d macro. The p mark needs to be set so there is a known point to jump to as this runs
  • o^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc> Writes the if/else statement text
  • 0*w*wyiWdd@0 actually executes the if statement.
  • Before executing this command, the line will contain @a @b 0 0 `pj@p @a 0 (@a%@b) `pdd@p 0 `dj@d
  • 0 moves the cursor to the beginning of the line

  • *w*w Moves the cursor to the code to execute next

    1. if @a == @b, that is `pj@p, which moves to the next number for @a and runs @p on it.
    2. if @a != @b and @a%@b == 0, that is `pdd@p, which deletes the current number @a, then runs @p on the next one.
    3. if @a != @b and @a%%b != 0, that is `dj@d, which checks the next number for @b to see if it is a factor of @a

  • yiWdd@0 yanks the command into the 0 register, deletes the line and runs the command

  • q ends the recording of the @d macro

• When this is first run, the `pdd@p command is run, deleting the N+1 line.

• qpmp"aywgg@dq writes the @p macro, which saves the number under the cursor, then goes to the first entry and runs @d on that.

• gg@p actually executes @p so that it will iterate over the whole file.

Answer 4

Haskell, 72 89 chars, O(n^2), Score 7921

Highest score per char count wins right? Modified for first N. Also I apparently can't use a calculator, so my score is not as abysmally bad as I thought. (using the complexity for basic trial division as found in the source below).

As per Will Ness the below is not a full Haskell program (it actually relies on the REPL). The following is a more complete program with a pseudo-sieve (the imports actually save a char, but I dislike imports in code golf).

main=getLine>>= \x->print.take(read x).(let s(x:y)=x:s(filter((>0).(`mod`x))y)in s)$[2..]

This version is undoubtedly (n^2). The algorithm is just a golf version of the naive ``sieve'', as seen here Old ghci 1 liner

getLine>>= \x->print.take(read x)$Data.List.nubBy(\x y->x`mod`y==0)[2..]

Leaving up the old, cheating answer because the library it links to is pretty nice.

print$take(10^6)Data.Numbers.Primes.primes

See here for an implementation and the links for the time complexity. Unfortunately wheels have a log(n) lookup time, slowing us down by a factor.

Answer 5

C#, 447 Characters, Bytes 452, Score ?

using System;namespace PrimeNumbers{class C{static void GN(ulong n){ulong primes=0;for (ulong i=0;i<(n*3);i++){if(IP(i)==true){primes++;if(primes==n){Console.WriteLine(i);}}}}static bool IP(ulong n){if(n<=3){return n>1;}else if (n%2==0||n%3==0){return false;}for(ulong i=5;i*i<=n;i+=6){if(n%i==0||n%(i+2)==0){return false;}}return true;}static void Main(string[] args){ulong n=Convert.ToUInt64(Console.ReadLine());for(ulong i=0;i<n;i++){GN(i);}}}}

scriptcs Variant, 381 Characters, 385 Bytes, Score ?

using System;static void GetN(ulong n){ulong primes=0;for (ulong i=0;i<(n*500);i++){if(IsPrime(i)==true){primes++;if(primes==n){Console.WriteLine(i);}}}}public static bool IsPrime(ulong n){if(n<=3){return n>1;}else if (n%2==0||n%3==0){return false;}for(ulong i=5;i*i<=n;i+=6){if(n%i==0||n%(i+2)==0){return false;}}return true;}ulong n=Convert.ToUInt64(Console.ReadLine());for(ulong i=0;i<n;i++){GetN(i);}

If you install scriptcs then you can run it.

P.S. I wrote this in Vim :D

Answer 6

GolfScript (45 chars, score claimed ~7708)

~[]2{..3${1$\%!}?={.@\+\}{;}if)1$,3$<}do;\;n*

This does simple trial division by primes. If near the cutting edge of Ruby (i.e. using 1.9.3.0) the arithmetic uses Toom-Cook 3 multiplication, so a trial division is O(n^1.465) and the overall cost of the divisions is O((n ln n)^1.5 ln (n ln n)^0.465) = O(n^1.5 (ln n)^1.965)†. However, in GolfScript adding an element to an array requires copying the array. I've optimised this to copy the list of primes only when it finds a new prime, so only n times in total. Each copy operation is O(n) items of size O(ln(n ln n)) = O(ln n)†, giving O(n^2 ln n).

And this, boys and girls, is why GolfScript is used for golfing rather than for serious programming.

† O(ln (n ln n)) = O(ln n + ln ln n) = O(ln n). I should have spotted this before commenting on various posts...

Answer 7

Scala 263 characters

Updated to fit to the new requirements. 25% of the code deal with finding a reasonable upper bound to calculate primes below.

object P extends App{
def c(M:Int)={
val p=collection.mutable.BitSet(M+1)
p(2)=true
(3 to M+1 by 2).map(p(_)=true)
for(i<-p){
var j=2*i;
while(j<M){
if(p(j))p(j)=false
j+=i}
}
p
}
val i=args(0).toInt
println(c(((math.log(i)*i*1.3)toInt)).take(i).mkString("\n"))
}

I got a sieve too.

Here is an empirical test of the calculation costs, ungolfed for analysis:

object PrimesTo extends App{
    var cnt=0
    def c(M:Int)={
        val p=(false::false::true::List.range(3,M+1).map(_%2!=0)).toArray
        for (i <- List.range (3, M, 2)
            if (p (i))) {
                var j=2*i;
                while (j < M) {
                    cnt+=1
                    if (p (j)) 
                        p(j)=false
                    j+=i}
            }
        (1 to M).filter (x => p (x))
    }
    val i = args(0).toInt
    /*
        To get the number x with i primes below, it is nearly ln(x)*x. For small numbers 
        we need a correction factor 1.13, and to avoid a bigger factor for very small 
        numbers we add 666 as an upper bound.
    */
    val x = (math.log(i)*i*1.13).toInt+666
    println (c(x).take (i).mkString("\n"))
    System.err.println (x + "\tcount: " + cnt)
}
for n in {1..5} ; do i=$((10**$n)); scala -J-Xmx768M P $i ; done 

leads to following counts:

List (960, 1766, 15127, 217099, 2988966)

I'm not sure how to calculate the score. Is it worth to write 5 more characters?

scala> List(4, 25, 168, 1229, 9592, 78498, 664579, 5761455, 50847534).map(x=>(math.log(x)*x*1.13).toInt+666) 
res42: List[Int] = List(672, 756, 1638, 10545, 100045, 1000419, 10068909, 101346800, 1019549994)

scala> List(4, 25, 168, 1229, 9592, 78498, 664579, 5761455, 50847534).map(x=>(math.log(x)*x*1.3)toInt) 
res43: List[Int] = List(7, 104, 1119, 11365, 114329, 1150158, 11582935, 116592898, 1172932855)

For bigger n it reduces the calculations by about 16% in that range, but afaik for the score formula, we don't consider constant factors?

new Big-O considerations:

To find 1 000, 10 000, 100 000 primes and so on, I use a formula about the density of primes x=>(math.log(x)*x*1.3 which determines the outer loop I'm running.

So for values i in 1 to 6=> NPrimes (10^i) runs 9399, 133768 ... times the outer loop.

I found this O-function iteratively with help from the comment of Peter Taylor, who suggested a much higher value for exponentiation, instead of 1.01 he suggested 1.5:

def O(n:Int) = (math.pow((n * math.log (n)), 1.01)).toLong

O: (n: Int)Long

val ns = List(10, 100, 1000, 10000, 100000, 1000*1000).map(x=>(math.log(x)*x*1.3)toInt).map(O) 

ns: List[Long] = List(102, 4152, 91532, 1612894, 25192460, 364664351)

 That's the list of upper values, to find primes below (since my algorithm has to know this value before it has to estimate it), send through the O-function, to find similar quotients for moving from 100 to 1000 to 10000 primes and so on: 

(ns.head /: ns.tail)((a, b) => {println (b*1.0/a); b})
40.705882352941174
22.045279383429673
17.62109426211598
15.619414543051187
14.47513863274964
13.73425213148954

This are the quotients, if I use 1.01 as exponent. Here is what the counter finds empirically:

ns: Array[Int] = Array(1628, 2929, 23583, 321898, 4291625, 54289190, 660847317)

(ns.head /: ns.tail)((a, b) => {println (b*1.0/a); b})
1.799140049140049
8.051553431205189
13.649578085909342
13.332251210010625
12.65003116535112
12.172723833234572

The first two values are outliers, because I have make a constant correction for my estimation formular for small values (up to 1000).

With Peter Taylors suggestion of 1.5 it would look like:

245.2396265560166
98.8566987153728
70.8831374743478
59.26104390040363
52.92941829568069
48.956394784317816

Now with my value I get to:

O(263)
res85: Long = 1576

But I'm unsure, how close I can come with my O-function to the observed values.

Answer 8

QBASIC, 98 Chars, Complexity N Sqrt(N), Score 970

I=1
A:I=I+2
FOR J=2 TO I^.5
    IF I MOD J=0 THEN GOTO A
NEXT
?I
K=K+1
IF K=1e6 THEN GOTO B
GOTO A
B:

Answer 9

Ruby 66 chars, O(n^2) Score - 4356

lazy is available since Ruby 2.0, and 1.0/0 is a cool trick to get an infinite range:

(2..(1.0/0)).lazy.select{|i|!(2...i).any?{|j|i%j==0}}.take(n).to_a

Answer 10

Ruby, 84 chars, 84 bytes, score?

This one is probably a little too novice for these parts, but I had a fun time doing it. It simply loops until f (primes found) is equal to n, the desired number of primes to be found.

The fun part is that for each loop it creates an array from 2 to one less than the number being inspected. Then it maps each element in the array to be the modulus of the original number and the element, and checks to see if any of the results are zero.

Also, I have no idea how to score it.

Update

Code compacted and included a (totally arbitrary) value for n

n,f,i=5**5,0,2
until f==n;f+=1;p i if !(2...i).to_a.map{|j|i%j}.include?(0);i+=1;end

Original

f, i = 0, 2
until f == n
  (f += 1; p i) if !(2...i).to_a.map{|j| i % j}.include?(0)
  i += 1
end

The i += 1 bit and until loop are sort of jumping out at me as areas for improvement, but on this track I'm sort of stuck. Anyway, it was fun to think about.

Answer 11

Perl - 94 characters, O(n log(n)) - Score: 427

perl -wle '$n=1;$t=1;while($n<$ARGV[0]){$t++;if((1x$t)!~/^1?$|^(11+?)\1+$/){print $t;$n++;}}'

Python - 113 characters

import re
z = int(input())
n=1
t=1
while n<z:
    t+=1
    if not re.match(r'^1?$|^(11+?)\1+$',"1"*t):
        print t
        n+=1

Answer 12

Scala, 124 characters

object Q extends App{Stream.from(2).filter(p=>(2 to p)takeWhile(i=>i*i<=p)forall{p%_!= 0})take(args(0)toInt)foreach println}

Simple trial division up to square root. Complexity therefore should be O(n^(1.5+epsilon))

124^1.5 < 1381, so that would be my score i guess?

Answer 13

AWK, 96 86 bytes

Subtitle: Look Mom! Only adding and some bookkeeping!

File fsoe3.awk:

{for(n=2;l<$1;){if(n in L)p=L[n]
else{print p=n;l++}
for(N=p+n++;N in L;)N+=p
L[N]=p}}

Run:

$ awk -f fsoe3.awk <<< 5
2
3
5
7
11
$ awk -f fsoe3.awk <<< 1000 | wc -l
1000

---

BASH, 133 bytes

File x.bash:

a=2
while((l<$1));do if((b[a]))
then((c=b[a]));else((c=a,l++));echo $a;fi;((d=a+c))
while((b[d]));do((d+=c));done
((b[d]=c,a++));done

Run:

$ bash x.bash 5
2
3
5
7
11
$ bash x.bash 1000 | wc -l
1000

---

Primes get calculated by letting the already found primes jump on the "tape of positive integers". Basically it is a serialised Sieve Of Eratosthenes.

from time import time as t

L = {}
n = 2
l = 0

t0=t()

while l<1000000:

        if n in L:
                P = L[n]
        else:
                P = n
                l += 1
                print t()-t0

        m = n+P
        while m in L:
                m += P
        L[m] = P

        n += 1

...is the same algorithm in Python and prints out the time when the l-th prime was found instead of the prime itself.

The output plotted with gnuplot yields the following:

The jumps probably have something to do with file i/o delays due to writing buffered data to disk...

Using much larger numbers of primes to find, will bring additional system dependent delays into the game, e.g. the array representing the "tape of positive integers" grows continuously and sooner or later will make every computer cry for more RAM (or later swap).

...so getting an idea of the complexity by looking at the experimental data does not really help a lot... :-(

---

Now counting the additions needed to find n primes:

cells = {}
current = 2
found = 0

additons = 0

while found < 10000000:

        if current in cells:
                candidate = cells[current]
                del cells[current] # the seen part is irrelevant
        else:
                candidate = current
                found += 1 ; additons += 1
                print additons

        destination = current + candidate ; additons += 1
        while destination in cells:
                destination += candidate ; additons += 1
        cells[destination] = candidate

        current += 1 ; additons += 1

Answer 14

awk 45 (complexity N^2)

another awk, for primes up to 100 use like this

awk '{for(i=2;i<=sqrt(NR);i++) if(!(NR%i)) next} NR>1' <(seq 100)

code golf counted part is

{for(i=2;i<=sqrt(NR);i++)if(!(NR%i))next}NR>1

which can be put in a script file and run as awk -f prime.awk <(seq 100)

Answer 15

Scala 121 (99 without the Main class boilerplate)

object Q extends App{Stream.from(2).filter{a=>Range(2,a).filter(a%_==0).isEmpty}.take(readLine().toInt).foreach(println)}

Answer 16

Python 3, 117 106 bytes

This solution is slightly trivial, as it outputs 0 where a number is not prime, but I'll post it anyway:

r=range
for i in[2]+[i*(not 0 in[i%j for j in r(3,int(i**0.5)+1,2)])for i in r(3,int(input()),2)]:print(i)

Also, I'm not sure how to work out the complexity of an algorithm. Please don't downvote because of this. Instead, be nice and comment how I could work it out. Also, tell me how I could shorten this.

Answer 17

Haskell (52²=2704)

52`take`Data.List.nubBy(((1<).).gcd)[2..]`forM_`print

Answer 18

Perl 6, 152 bytes, O(n log n log (n log n) log (log (n log n))) (?), 9594.79 points

According to this page, the bit complexity of finding all primes up to n is O(n log n log log n); the complexity above uses the fact that the nth prime is proportional to n log n.

my \N=+slurp;my \P=N*(N.log+N.log.log);my @a=1 xx P;for 2..P.sqrt ->$i {if @a[$i] {@a[$_*$i]=0 for $i..P/$i}};say $_[1] for (@a Z ^P).grep(*[0])[2..N+1]

Answer 19

Groovy (50 Bytes) - O(n*sqrt(n)) - Score 353.553390593

{[1,2]+(1..it).findAll{x->(2..x**0.5).every{x%it}}​}​

Takes in n and outputs all numbers from 1 to n which are prime.

The algorithm I chose only outputs primes n > 2, so adding 1,2 at the beginning is required.

Breakdown

x%it - Implicit truthy if it is not divisible, falsy if it is.

(2..x**0.5).every{...} - For all the values between 2 and sqrt(x) ensure that they are not divisible, for this to return true, must return true for every.

(1..it).findAll{x->...} - For all values between 1 and n, find all that fit the criteria of being non-divisible between 2 and sqrt(n).

{[1,2]+...}​ - Add 1 and 2, because they are always prime and never covered by algorithm.

Answer 20

Racket 155 bytes

(let p((o'(2))(c 3))(cond[(>=(length o)n)(reverse o)][(ormap(λ(x)(= 0(modulo c x)))
(filter(λ(x)(<= x(sqrt c)))o))(p o(add1 c))][(p(cons c o)(add1 c))]))

It keeps a list of prime numbers found and checks divisibility of each next number by primes already found. Moreover, it checks only upto the square root of number being tested since that is enough.

Ungolfed:

(define(nprimes n)
  (let loop ((outl '(2))                   ; outlist having primes being created
             (current 3))                  ; current number being tested
  (cond
    [(>= (length outl) n) (reverse outl)]  ; if n primes found, print outlist.
    [(ormap (λ(x) (= 0 (modulo current x))) ; test if divisible by any previously found prime
            (filter                         ; filter outlist till sqrt of current number
             (λ(x) (<= x (sqrt current)))
             outl))
     (loop outl (add1 current)) ]           ; goto next number without adding to prime list
    [else (loop (cons current outl) (add1 current))] ; add to prime list and go to next number
    )))

Testing:

(nprimes 35)

Output:

'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149)

Answer 21

Javascript, 61 chars

f=(n,p=2,i=2)=>p%i?f(n,p,++i):i==p&&n--&alert(p)||n&&f(n,++p)

A bit worse than O(n^2), will run out of stack space for large n.