GolfScript, 25 (24) bytes

!10 6?,2>{.(@*.)@%!},n*\;

If the output format specified in the edited question is disregarded, one byte can be saved:

!10 6?,2>{.(@*.)@%!},`\;

This will print the primes as an array (like many other solutions do) rather than one per line.

How it works

The general idea is to use Wilson's theorem, which states that n > 1 is prime if and only if

!     # Push the logical NOT of the empty string (1). This is an accumulator.
10 6? # Push 10**6 = 1,000,000.
,2>   # Push [ 2 3 4 … 999,999 ].
{     # For each “N” in this array:
  .(  # Push “N - 1”.
  @   # Rotate the accumulator on top of the stack.
  *   # Multiply it with “N - 1”. The accumulator now hold “(N - 1)!”.
  .)  # Push “(N - 1)! + 1”
  @   # Rotate “N” on top of the stack.
  %!  # Push the logical NOT of “((N - 1)! + 1) % N”.
},    # Collect all “N” for which “((N - 1)! + 1) % N == 0” in an array.
n*    # Join that array by LF.
\;    # Discard the accumulator.

Benchmarks

Faster than trial division, but slower than the sieve of Eratosthenes. See my other answer.

GolfScript, 25 (24) bytes

!10 6?,2>{.(@*.)@%!},n*\;

If the output format specified in the edited question is disregarded, one byte can be saved:

!10 6?,2>{.(@*.)@%!},`\;

This will print the primes as an array (like many other solutions do) rather than one per line.

How it works

The general idea is to use Wilson's theorem, which states that n > 1 is prime if and only if

!     # Push the logical NOT of the empty string (1). This is an accumulator.
10 6? # Push 10**6 = 1,000,000.
,2>   # Push [ 2 3 4 … 999,999 ].
{     # For each “N” in this array:
  .(  # Push “N - 1”.
  @   # Rotate the accumulator on top of the stack.
  *   # Multiply it with “N - 1”. The accumulator now hold “(N - 1)!”.
  .)  # Push “(N - 1)! + 1”
  @   # Rotate “N” on top of the stack.
  %!  # Push the logical NOT of “((N - 1)! + 1) % N”.
},    # Collect all “N” for which “((N - 1)! + 1) % N == 0” in an array.
n*    # Join that array by LF.
\;    # Discard the accumulator.

Benchmarks

Faster than trial division, but slower than the sieve of Eratosthenes. See my other answer.

GolfScript, 25 (24) bytes

!10 6?,2>{.(@*.)@%!},n*\;

If the output format specified in the edited question is disregarded, one byte can be saved:

!10 6?,2>{.(@*.)@%!},`\;

This will print the primes as an array (like many other solutions do) rather than one per line.

How it works

The general idea is to use Wilson's theorem, which states that n > 1 is prime if and only if

!     # Push the logical NOT of the empty string (1). This is an accumulator.
10 6? # Push 10**6 = 1,000,000.
,2>   # Push [ 2 3 4 … 999,999 ].
{     # For each “N” in this array:
  .(  # Push “N - 1”.
  @   # Rotate the accumulator on top of the stack.
  *   # Multiply it with “N - 1”. The accumulator now hold “(N - 1)!”.
  .)  # Push “(N - 1)! + 1”
  @   # Rotate “N” on top of the stack.
  %!  # Push the logical NOT of “((N - 1)! + 1) % N”.
},    # Collect all “N” for which “((N - 1)! + 1) % N == 0” in an array.
n*    # Join that array by LF.
\;    # Discard the accumulator.

Benchmarks

Faster than trial division, but slow. See my other answer.

GolfScript, 25 (24) bytes

!10 6?,2>{.(@*.)@%!},n*\;

If the output format specified in the edited question is disregarded, one byte can be saved:

!10 6?,2>{.(@*.)@%!},`\;

This will print the primes as an array (like many other solutions do) rather than one per line.

How it works

The general idea is to use Wilson's theorem, which states that n > 1 is prime if and only if

!     # Push the logical NOT of the empty string (1). This is an accumulator.
10 6? # Push 10**6 = 1,000,000.
,2>   # Push [ 2 3 4 … 999,999 ].
{     # For each “N” in this array:
  .(  # Push “N - 1”.
  @   # Rotate the accumulator on top of the stack.
  *   # Multiply it with “N - 1”. The accumulator now hold “(N - 1)!”.
  .)  # Push “(N - 1)! + 1”
  @   # Rotate “N” on top of the stack.
  %!  # Push the logical NOT of “((N - 1)! + 1) % N”.
},    # Collect all “N” for which “((N - 1)! + 1) % N == 0” in an array.
n*    # Join that array by LF.
\;    # Discard the accumulator.

Benchmarks

Faster than trial division, but slower than the sieve of Eratosthenes. See my other answer.

Competitiveness

In absence of any built-in mathematical functions to factorize or check for primality (or even compute factorials, for that matter), all GolfScript solutions will either be very large or very inefficient.

While still far from being efficient, my approach is a lot faster than trial division and – at the time of its submission – it seems to be the shortest of all approaches that do not use any of those built-ins. I say seems because I have no idea how some of the answers work.

I've compared my solution to that of w0lf, which implements trial division in GolfScript and has the same byte count:

Primes    | Trial division     | Wilson's theorem
----------+--------------------+------------------
1,000     | 2.47 s             | 0.03 s
10,000    | 246.06 s (~ 4 m)   | 0.38 s
20,000    | 1006.83 s (~17 m)  | 1.41 s
100,000   | ~ 7 h (estimated)  | 35.20 s
1,000,000 | ~ 29 d (estimated) | 3695.92 s (~ 1 h)

Benchmarks

Faster than trial division, but slow. See my other answer.