[Question]
  [
This is my first code golf question, and a very simple one at that, so I apologise in advance if I may have broken any community guidelines.
The task is to print out, in ascending order, all of the prime numbers less than a million. The output format should be one number per line of output.
The aim, as with most code golf submissions, is to minimise code size. Optimising for runtime is also a bonus, but is a secondary objective.
  
[Answer]
## [Python 3](https://docs.python.org/3/), 45 bytes
```
k=P=1
while k<1e6:P%k>0==print(k);P*=k*k;k+=1
```
[Try it online!](https://tio.run/##K6gsycjPM/7/P9s2wNaQqzwjMydVIdvGMNXMKkA1287A1ragKDOvRCNb0zpAyzZbK9s6W9vW8P9/AA "Python 3 – Try It Online")
By the time the loop reaches testing `k`, it has iteratively computed the squared-factorial `P=(k-1)!^2`. If `k` is prime, then it doesn't appear in the product `1 * 2 * ... * (k-1)`, so it's not a factor of `P`. But, if it's composite, all its prime factors are smaller and so in the product. The squaring is only actually needed to stop `k=4` from falsely being called prime.
More strongly, it follows from [Wilson's Theorem](https://en.wikipedia.org/wiki/Wilson%27s_theorem) that when `k` is prime, `P%k` equals `1`. Though we only need that it's nonzero here, it's useful in general that `P%k` is an indicator variable for whether `k` is prime.
Thanks to @Sisyphus for 1 byte with `P%k>0==print(k)` using chained operator short-circuiting in place of `P%k and print(k)`.
[Answer]
### *Mathematica*, ~~17~~ 24
Just for comparison:
```
Prime@Range@78498
```
*As noted in a comment I failed to provide one prime per line; correction:*
```
Column@Prime@Range@78498
```
[Answer]
## C, 61 chars
Almost exactly the same as [this one](https://codegolf.stackexchange.com/a/5818/3544) (the question is almost exactly the same too).
```
n=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:n%m?m-1:n++);}
```
[Answer]
### MATLAB (16) (12)
Unfortunately, this outputs on a single line:
```
primes(1000000)
```
but that is solved by a simple matrix transpose:
```
primes(1000000)'
```
and I can cut out some characters by using exponential notation (as suggested in the comments):
```
primes(1e6)'
```
[Answer]
## Bash (37 chars)
```
seq 2 1e6|factor|sed 's/.*: //g;/ /d'
```
## (60 chars)
```
seq 2 1000000|factor|sed -e 's/[0-9]*: //g' -e '/^.* .*$/ d'
```
on my computer (2.0 GHz cpu, 2 GB ram) takes 14 seconds.
[Answer]
## J, 21 characters
```
1[\p:i.(_1 p:1000000)
```
which can be shortened to 
```
1[\p:i.78498
```
if you know how many primes there are below 1000000.
[Answer]
# Bash, 30 bytes
Since [saeedn](https://codegolf.stackexchange.com/u/3115) won't act on my suggestion – which is both shorter and faster than his approach – I thought I'd post my own answer:
```
seq 1e6|factor|awk '$0=$2*!$3'
```
### How it works
```
seq 1e6
```
lists all positive integers up to 1,000,000.
```
factor
```
factors them one by one. For the first ten, the output is the following:
```
1:
2: 2
3: 3
4: 2 2
5: 5
6: 2 3
7: 7
8: 2 2 2
9: 3 3
10: 2 5
```
Finally,
```
awk '$0=$2*!$3'
```
changes the entire line (`$0`) to the product of the second field (the first prime factor) and the logical negation of the third field (`1` if the is one prime factor or less, `0` otherwise).
This replaces lines corresponding to prime numbers with the number itself and all other lines with zeros. Since awk only prints truthy values, only prime number will get printed.
[Answer]
# Ruby 34
```
require'prime';p Prime.take 78498
```
[Answer]
# PowerShell, 47 44 bytes
Very slow, but the shortest I could come up with.
```
$p=2..1e6;$p|?{$n=$_;!($p-lt$_|?{!($n%$_)})}
```
# PowerShell, 123 bytes
This is much faster; far from optimal, but a good compromise between efficiency and brevity.
```
 $p=2..1e6;$n=0
 while(1){$p=@($p[0..$n]|?{$_})+($p[($n+1)..($p.count-1)]|?{$_%$p[$n]});$n++;if($n-ge($p.count-1)){break}}
 $p
```
[Answer]
# Bash, 37
Will golf more, if I can...
Most of this is trying to parse `factor`'s awkward output format.
```
seq 1e6|factor|grep -oP "(?<=: )\d+$"
```
Takes 5.7 or so seconds to complete on my machine.
(It just happened that *my* post was the *first* to go on the second page of answers, so nobody is going to see it...)
## Old solution
This is longer and slower (takes 10 seconds).
```
seq 1e6|factor|egrep ':.\S+$'|grep -oE '\S+$'
```
[Answer]
# Python 3.x: 66 chars
```
for k in range(2,10**6):
 if all(k%f for f in range(2,k)):print(k)
```
# More efficient solution: 87 chars
Based on the Sieve of Eratosthenes.
```
p=[];z=range(2,10**6)
while z:f=z[0];p+=[f];z=[k for k in z if k%f]
for k in p:print(k)
```
[Answer]
# Haskell, 51
```
mapM print [n|n<-[2..10^6],all((>0).rem n)[2..n-1]]
```
[Answer]
### Ruby ~~50~~ 41
```
require'mathn'
p (2..1e6).select &:prime?
```
[Answer]
# Julia, 11
```
primes(10^6)
```
It looks like built ins are getting upvotes, plus I needed more words for longer answer.
[Answer]
## APL, 15
```
p~,p∘.×p←1↓⍳1e6
```
My interpreter ran into memory problems, but it works in theory.
[Answer]
# Perl, 49 bytes
Regular expression kung fu :)
```
for(1..1E6){(1x$_)=~/^(11+?)\1+$/ or print"$_\n"}
```
Ungolfed version:
```
for(1 .. 1_000_000) { 
    (1x$_) =~ /^(11+?)\1+$/ or print "$_\n";
}
```
It hasn't even made 10% progress while I type this post!
Source for the regex: <http://montreal.pm.org/tech/neil_kandalgaonkar.shtml>
[Answer]
# J (15 or 9)
I can't believe this beat Mathematica (even if it's just ~~a single~~ by 2 chars)
```
a#~1 p:a=:i.1e6
```
Or:
```
p:i.78498
```
[Answer]
# gs2, 5 bytes
Encoded in CP437:
```
∟)◄lT
```
`1C 29` pushes a million, `11 6C` is primes below, `54` is show lines.
[Answer]
## C, 91 88 85 82 81 80 76 72 characters
```
main(i,j,b){for(;i++<1e6;b++&&printf("%d\n",i))for(j=2;j<i;)b=i%j++&&b;}
```
The algorithm is terribly inefficient, but since we're doing code-golf that shouldn't matter.
[Answer]
# GolfScript, 22/20 (20/19) bytes
```
n(6?,:|2>{(.p|%-.}do:n
```
At the cost of speed, the code can be made two bytes shorter:
```
n(6?,:|2>.{|%2>-}/n*
```
If the output format specified in the edited question is disregarded (which is what many of the existing answers do), two bytes can be saved in the fast version and one can be saved in the slow one:
```
n(6?,:|2>{(.p|%-.}do
n(6?,:|2>.{|%2>-}/`
```
This will print an additional LF after the primes for the fast version, and it will print the primes as an array for the slow one.
### How it works
Both versions are implementations of the [sieve of Eratosthenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes "Sieve of Eratosthenes - Wikipedia, the free encyclopedia").
The fast version does the following:
1. Set `A = [ 2 3 4 … 999,999 ]` and `| = [ 0 1 2 … 999,999 ]`.
2. Set `N = A[0]` and print `N`.
3. Collect every N-th element from `|` in `C`. These are the multiples of `N`.
4. Set `A = A - C`.
5. If `A` is non-empty, go back to 2.
```
n(6?   # Push "\n".pop() ** 6 = 1,000,000.
,:|    # Push | = [ 0 1 2 … 999,999 ].
,2>    # Push A = [ 2 3 4 … 999,999 ].
{      #
  (    # Unshift the first element (“N”) of “A”.
  .p   # Print “N”.
  |%   # Collect every N-th element from “A” into a new array, starting with the first.
  -    # Take the set difference of “A” and the array from above.
  .    # Duplicate the set difference.
}do    # If the set difference is non-empty, repeat.
:n     # Store the empty string in “n”, so no final LF will get printed.
```
The slow version works in a similar fashion, but instead of successively removing multiples of the minimum of “A” (which is always prime), it removes multiples of all positive integers below 1,000,000.
### Competitiveness
In absence of any built-in mathematical functions to factorize or check for primality, all GolfScript solutions will either be very large or very inefficient.
While still far from being efficient, I think I have achieved a decent speed-to-size ratio. At the time of its submission, this approach seems to be the shortest of those that do not use any of the aforementioned built-ins. I say *seems* because I have no idea how some of the answers work...
I've benchmarked all four submitted GolfScript solutions: [w0lf's](https://codegolf.stackexchange.com/a/5987) (trial division), [my other answer](https://codegolf.stackexchange.com/a/27063) (Wilson's theorem) and the two of this answer. These were the results:
```
Bound     | Trial division     | Sieve (slow)       | Wilson's theorem | Sieve (fast)
----------+--------------------+--------------------+------------------+----------------
1,000     | 2.47 s             | 0.06 s             | 0.03 s           | 0.03 s
10,000    | 246.06 s (4.1 m)   | 1.49 s             | 0.38 s           | 0.14 s
20,000    | 1006.83 s (16.8 m) | 5.22 s             | 1.41 s           | 0.38 s
100,000   | ~ 7 h (estimated)  | 104.65 (1.7 m)     | 35.20 s          | 5.82 s
1,000,000 | ~ 29 d (estimated) | 111136.97s (3.1 h) | 3695.92 s (1 h)  | 418.24 s (7 m)
```
[Answer]
# NARS2000 APL, 7 characters
```
⍸0π⍳1e6
```
[Answer]
## Golfscript ~~26 25~~ 24
### Edit (saved one more char thanks to Peter Taylor):
```
10 6?,{:x,{)x\%!},,2=},`
```
Old code:
```
10 6?,{.,{)\.@%!},,2=*},`
```
This code has only theoretical value, as it is incredibly slow and inefficient. I think it could take hours to run.
If you wish to test it, try for example only the primes up to 100:
```
10 2?,{:x,{)x\%!},,2=},`
```
[Answer]
# CJam - 11
```
1e6,{mp},N*
```
`1e6,` - array of 0 ... 999999  
`{mp},` - select primes  
`N*` - join with newlines
[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](http://en.wikipedia.org/wiki/Wilson's_theorem "Wilson's theorem - Wikipedia, the free encyclopedia"), which states that *n* > 1 is prime if and only if
                                                      ![(n - 1)! = -1 (mod n)](https://i.stack.imgur.com/2ALVY.png)
```
!     # 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](https://codegolf.stackexchange.com/a/27066/).
[Answer]
# Java, 110 bytes
```
void x(){for(int i=1;i++<1e6;)System.out.print(new String(new char[i]).matches(".?|(..+?)\\1+")?"":(i+"\n"));}
```
Using unary division through regex as a primality test.
[Answer]
# [Julia 1.x](http://julialang.org/), 38 bytes
```
2:1e6 .|>i->0∉i.%(2:i-1)==println(i)
```
[Try it online!](https://tio.run/##yyrNyUw0rPj/38jKMNVMQa/GLlPXzuBRR2emnqqGkVWmrqGmrW1BUWZeSU6eRqbm//8A "Julia 1.0 – Try It Online")
Since the [other Julia answer](https://codegolf.stackexchange.com/a/27021/48931) was posted, `primes` is no longer in the standard library. We use a couple of features:
* `∉` costs 3 bytes but is shorter than `in(...)`.
* We use the map syntax `f.x` over `map(f,x)`.
* We can broadcast `%` using `.%`.
* Floating point can exactly represent everything up to `1e6`, no problems there.
* We use a `==` short circuiting trick.
[Answer]
# Mathematica 25
Assuming you don't know the number of primes less than 10^6:
```
Prime@Range@PrimePi[10^6]
```
[Answer]
# J, 16 chars
```
1]\(#~1&p:)i.1e6
```
Without the output format requirement, this can be reduced to **13** chars:
```
(#~1&p:)i.1e6
```
`1]\` just takes the rank 1 array of primes, turns it into a rank 2 array, and puts each prime on its own row -- and so the interpreter's default output format turns the one line list into one prime per line.
`(#~ f) y` is basically `filter`, where `f` returns a boolean for each element in `y`. `i.1e6` is the range of integers [0,1000000), and `1&p:` is a boolean function that returns 1 for primes.
[Answer]
## R, ~~45~~ 43 characters
```
for(i in 2:1e6)if(sum(!i%%2:i)<2)cat(i," ")
```
For each number x from 2 to 1e6, simply output it if the number of x mod 2 to x that are equal to 0 is less than 2.
[Answer]
# Bash (433643)
My (not so clever) attempt was to use factor to factor the product.
```
factor ${PRODUCT}
```
Unfortunately with large numbers the product is of course huge. It also took over 12 hours to run. I decided to post it though because I thought it was unique.
[Here is the full code.](http://pastebin.com/TYQLBZ5d)
If it was primes under six it would be reasonable.
```
  factor 30
```
Oh well, I tried.
]