List of first n prime numbers most efficiently and in shortest code 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.
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.