List of primes under a million

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 1

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 2

Python 3, 46 bytes

k=P=1
while k<1e6:P%k and print(k);P*=k*k;k+=1

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

Answer 3

C, 61 chars

Almost exactly the same as this one (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 4

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 5

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 6

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 7

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 8

Ruby 34

require'prime';p Prime.take 78498

Answer 9

APL, 15

p~,p∘.×p←1↓⍳1e6

My interpreter ran into memory problems, but it works in theory.

Answer 10

Haskell, 51

mapM print [n|n<-[2..10^6],all((>0).rem n)[2..n-1]]

Answer 11

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 12

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 13

Bash, 30 bytes

Since saeedn 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 14

Ruby 50 41

require'mathn'
p (2..1e6).select &:prime?

Answer 15

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 16

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 17

Julia, 11

primes(10^6)

It looks like built ins are getting upvotes, plus I needed more words for longer answer.

Answer 18

gs2, 5 bytes

Encoded in CP437:

∟)◄lT

1C 29 pushes a million, 11 6C is primes below, 54 is show lines.

Answer 19

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.

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 (trial division), my other answer (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 20

NARS2000 APL, 7 characters

⍸0π⍳1e6

Answer 21

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.

Answer 22

CJam - 11

1e6,{mp},N*

1e6, - array of 0 ... 999999
{mp}, - select primes
N* - join with newlines

Answer 23

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 24

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 25

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 26

Mathematica 25

Assuming you don't know the number of primes less than 10^6:

Prime@Range@PrimePi[10^6]

Answer 27

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 28

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.

If it was primes under six it would be reasonable.

  factor 30

Oh well, I tried.

Answer 29

C#, 70

Enumerable.Range(1,1e6).Where(n=>Enumerable.Range(2,n).All(x=>x%n!=0))

You're not going to see much here though for a LONG time...

Answer 30

NARS2000 APL - 9 characters

¯2π⍳2π1e6

Quite a boring answer.

Short explanation:

¯2 π  ⍝ generate the Nth prime for N
⍳     ⍝ in the range 1 to
2 π   ⍝ the number of primes less than or equal to
1e6   ⍝ a million

Answer 31

HPPPL, 90 89 chars

(HP Prime Programming Language), for the HP Prime color graphing calculator.

export p()begin local i;for i from 2 to 1e6 do if isprime(i)=1 then print(i) end;end;end;

Output to the terminal is quite slow on the Prime, so the program takes quite a while to run. Printing out all primes using the emulator takes about 88 seconds on my i5 2410M laptop.

As my google account is messed up, I have to start all over again with a new account... so be it. My photo and name are the same as before ;)

You can try out the program with the free HP Prime emulator available here:

http://www.hp-prime.de/en/category/13-emulator

Answer 32

F#, 100 94 bytes

let p n=
    let rec c i=i>n/2||(n%i<>0&&c(i+1))
    c 2
for n in 1..1000000 do if p n then printfn "%i" n

let p n={2..n-1}|>Seq.forall(fun x->n%x<>0)
{2..1000000}|>Seq.filter p|>Seq.iter(printfn "%i")

Answer 33

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 34

QBASIC, 75 bytes

FOR I=2 TO 1e6
    FOR J=2 TO I^.5
        IF I MOD J=0 THEN:GOTO X
    NEXT
    ?I
X:NEXT

I could have saved a character by going with FOR J = 2 TO I/2 but the run time was seriously slow. Runs at a much saner speed by only going to Sqrt I.

Answer 35

PHP, 55 53 51 bytes

for($n=1;1e6>$i=$n++;$i||print"$n
")while($n%$i--);

Run with -nr or try it online. (TiO only runs to 10K; 1M would exceed the time limit.)

The outer loop runs $n from 1 to 1 million.
The inner loop is the primality test: loops $i down from $n-1 until $i is a divisor of $n.
If that divisor is 1, $n is a prime and will be printed in the post-condition of the outer loop.

Answer 36

Javascript, 74 73 bytes

saved one byte thanks to Martin Ender

()=>{for(i=0;i<1e6;i++)!/^.?$|^(..+)\1+$/.test('1'.repeat(i))&&alert(i);}

Tests all numbers under 1 million against a regex. Regex Explanation

Answer 37

Jelly, 7 bytes

10*6ÆRY

Try it online!

10*6    # One million in scientific notation (10^6 = 1,000,000).
    ÆR  # List of primes less than one million.
      Y # Join the list with newlines.

Answer 38

Octave, 12, 11

primes(1e6)

Write 1000000 as 1e6

Answer 39

Befunge-98, 119 characters

Because if it can be done, it can be done in Befunge! Probably not optimal. Works in 98 but not 93 because of the difference in how many bits a cell can store.

2.300p210pv>a,00g:.2+00>p"d"::**v
>00g1-10g`!|Prime Get> ^|p012!`\<
| %g01g00 <>10g1+10pv  v<
>00g:2+00#^        #<^#<@

Answer 40

Python 2; 67 Bytes

n,p=3,[2]
while n<1e5:exec'print n;p+=[n]'*all(n%x for x in p);n+=2

Checks current number against all previous primes, and if not divisible by any of them, prints number and adds to list

The advantage of the while loop compared to other methods is that python will allow direct comparison against a number of the form "1e5", rather than having to use a long form or convert it to an int

Still takes a long time to run

Answer 41

FORTRAN 90, 80 bytes

DO I=2,1E2;D=1;DO J=2,I**.5;IF(MOD(I,J)==0)D=0;ENDDO;IF(D==1)PRINT*,I;ENDDO;END

This is the same as below, but in a newer and less rigorous version.

---

FORTRAN 77, 104 95 bytes

      DOI=2,1E6;D=1;DOJ=2,I**.5;IF(MOD(I,J).EQ.0)D=0;
      ENDDO;IF(D.EQ.1)PRINT*,I;ENDDO;END

Works with gfortran. Not sure if the DO I=... and DO J=... works without spaces in other compilers.

(Modification: program name supressed; I just learned that it's optional!)

Answer 42

05AB1E, 6 bytes

6°ÅPε,

Try it online!

Explanation:

6°ÅPε,
6°       Push 1000000 to stack (10^6)
  ÅP     List of all primes < 1000000
    ε,   Print each element of the list

Answer 43

Perl 6, 27 bytes

grep(&is-prime,^)>>.say

Try it online!

Filters all the primes from 0 to a million minus 1 and then prints.

Answer 44

PHP - 72 bytes

<?for($i=1;$i++^999999;print$d?~ı.$i:'')for($d=$j=2;$j<$i&&$d=$i%$j++;);

Hexdump:

0000000 3c 3f 66 6f 72 28 24 69 3d 31 3b 24 69 2b 2b 5e
0000010 39 39 39 39 39 39 3b 70 72 69 6e 74 24 64 3f 7e
0000020 f5 2e 24 69 3a 27 27 29 66 6f 72 28 24 64 3d 24
0000030 6a 3d 32 3b 24 6a 3c 24 69 26 26 24 64 3d 24 69
0000040 25 24 6a 2b 2b 3b 29 3b                        
0000048

Kinda slow, could be optimised (for 6 bytes) by division-checking until the square root of each number only, like so:

<?for($i=1;$i++^999999;print$d?~ı.$i:'')for($d=$j=2;$j<sqrt($i)&&$d=$i%$j++;);

Answer 45

Commodore 64 Basic, 55 characters

1F┌I=2TO10^6:F┌J=2TOI/2:IF(I/J=INT(I/I))G┌3
2N─:?I
3N─I

PETSCII substitutions: ┌ = SHIFT+O, ─ = SHIFT+E

Incredibly slow: first, because the algorithm is extremely inefficient (it tries dividing by every value less than half the candidate number), second, because the Commodore 64 is slow, and third, because Commodore Basic does all its math in emulated floating-point on an 8-bit CPU.

Theoretical solution, 82 characters

1M=10^6:D╮S(M):F┌I=2TO1000:F┌J=I^2TOMST─I:S(J)=-1:N─:N─:F┌I=2TOM:IF(N┌S(I))T|:?I
2N─

╮ = SHIFT+I, ┌ = SHIFT+O, ─ = SHIFT+E, | = SHIFT+H

If this program could run on an actual Commodore 64, it would be much faster than the above. However, it can't: the sieve alone would take 5,000,007 bytes out of the 38,911 bytes a C64 has available for Basic programs. Note the use of -1 instead of 1 when denoting composite values in the array: C64 Basic doesn't have a true boolean negation; NOT performs a two's complement instead.

Answer 46

PARI/GP, 26 bytes

Simple solution:

forprime(p=2,1e6,print(p))

Less-efficient solutions, one per line:

prodeuler(p=2,1e6,print(p));
apply(n->print(n),primes(78498));
apply(n->print(n),primes([2,1e6]));

Answer 47

APL (Dyalog), 15 chars

⍪(⊢~∘.×⍨)1↓⍳1E6

Try it online! (only goes until one thousand as TIO does not allot enough memory for a million)

⍳1E6 first million ɩntegers

1↓ drop one

(…) apply the following tacit function:

 ⊢ the argument (all the numbers 2…1000000)

 ~ except those that are in

 ∘.×⍨ the multiplication table (using the argument as both vertical and horizontal axis)

⍪ table (makes list into column)

Answer 48

Python, 75

print filter(lambda n:n==2 or all(n%i for i in range(2,n)),range(15485864))

Not terribly efficient though, it actually gives me a out of memory error in Jython.

Here's a (slightly) more efficient version:

import math
print [2]+filter(lambda n:all(n%i for i in xrange(3,int(math.sqrt(n))+1,2)),xrange(3,15485864,2))

This version took approximately 8 minutes to run.

Answer 49

Scala, 58

2 to 1000000 map{x=>if(2 to x/2 forall(x%_!=0))println(x)}

or

2 to 1000000 filter{x=>2 to x/2 forall(x%_!=0)}map println

Answer 50

Javascript es6 66 bytes

I was surprised to not see JS in here so I thought I'd put in a word for her

//takes about 19 minutes to run on my work pc
for(i=2,l=[];i<1e6;++i)l.every(a=>i/a%1)&&l.push(console.log(i)|i)

Answer 51

MATL, 5 bytes

1e6Zq

Explanation:

1e6   % push 10000 to stack
   Zq % primes up to top-of-stack number

Answer 52

Tcl, 104 bytes

set i 2
time {set p 1;set j 2;while \$j<$i {if $i%$j==0 {set p 0};incr j};if $p {puts $i};incr i} 999998

Try it online!

Unfortunately I could not find an online Tcl interpreter which does not time out running it.

---

Tcl, 110 bytes

set i 2
time {set p 1;set j 2;while \$j<$i {if $i%$j==0 {set p 0;break};incr j};if $p {puts $i};incr i} 999998

Try it online!

tcl, 115

set i 2
time {set p 1;set j 2;while \$j<$i {if ![expr $i%$j] {set p 0;break};incr j};if $p {puts $i};incr i} 999998

demo

---

tcl, 201

My still not golfed answer:

for {set i 2} {$i<$1000000} {incr i} {
    set p 1
    for {set j 2} {$j<$i} {incr j} {
        if {[expr $i%$j] == 0} {
            set p 0
            break
        }
    }

    if $p {puts $i}
}

demo

Answer 53

PHP, 100 95 bytes

It works by iterating 1,000,000 times and then using this regular expression on a unary number to check if it's prime. It's not the smallest PHP solution submitted, but thought I'd submit it just so it's here.

for($i=0;$i<=1e6;$i++)if(preg_match('/^1?$|^(11+?)\1+$/',str_repeat("1",$i))==0)echo$i.PHP_EOL;

Matchu explains how the regular expression works - https://stackoverflow.com/a/3296068/3000179

First 50: https://eval.in/746404

Answer 54

Ohm, 3 bytes (CP437)

Non-competitive, obviously, but I don't think anyone will mind since this question is almost 5 years old ;)

6°P

Answer 55

05AB1E, 7 bytes

Since there is not yet an answer in 05AB1E.

T6mGNp–

Try it online!

Answer 56

Haskell, 65 chars

main=print[x|x<-[2..999999::Int],null[i|i<-[2..x-1],mod x i==0]]

Answer 57

Pyth, 12 bytes

V^T6IqlPN1N

Explanation

V^T6 - For loop using looping variable N in range 0 to 10 ^ 6

IqlPN1 - If len(prime_factors(n)) == 1

N - implicity print n (if it is prime)

Try running the code here: https://pyth.herokuapp.com/?code=V%5ET6IqlPN1N&debug=0

Note that this seems to take too long to run on the online interpreter, so try replacing V^T6 with V^T3, which will run (and clearly if it can print primes up to 1,000, it will work with 1,000,000)

Answer 58

Pyt, 9 bytes

78497ǰƖřᵽ

Try it online!

78498ǰƖřᵽ
78497      - push 7, 8, 4, 9, and 7 on the stack
    ǰ      - join everything on stack w/no delimiters
     Ɩ     - casts to int
      ř    - construct range from 78498 to 1 ([1,2,3,..., 78497, 78498])
       ᵽ   - push xth prime for every item in list

Doesn't meet the timeout rq on tio, but it would work, you can try it with lower numbers the reason for 78498 is that that is the 0 indexed prime under a million

Answer 59

C (gcc) 65 bytes

j;f(i){for(;++i<1e6;)for(j=2;!printf("%d\n"+(i>j)*3,i)&&i%j++;);}

Try it online! ( stops at 1000 )

Answer 60

C - 67

$ cat x.c
main(p,t){for(p=1;t=2,++p<1e6;t<p||printf("%d\n",p))while(p%t++);}
$ wc -c x.c 
67 x.c
$ gcc -O3 x.c -o x
x.c: In function ‘main’:
x.c:1: warning: incompatible implicit declaration of built-in function ‘printf’
$ ./x | wc -l
78498

It's sloooooow... don't ask... :-D

I got an even shorter variant (54 bytes) but unluckily it prints the biggest prime first. ;-(

Maybe it fits in a different code golf... someday... ;-)

Answer 61

Clojure - 95 bytes

This is a simple, unoptimised function which prints the primes.

(defn p[](doseq[i(range 2 1e6):when(every? false?(map #(=(mod i %)0)(range 2 i)))](println i)))

Now, I wanted to create something nice too, so here is a function that creates a lazy infinite list of primes.

(defn primes
  ([]
    (concat [2 3] (primes 5)))
  ([n]
    (lazy-seq
      (first
        (for [i     (range)
              :let  [i (+ i n)]
              :when (every? false? (map #(= (mod i %) 0)
                                        (range 2 (Math/sqrt i))))]
          (cons i (primes (+ i 2))))))))

Answer 62

Matlab (12)

Pretty simple=)

primes(1e6)'

Answer 63

Java, 183 characters

import java.util.stream.*;
class P{public static void main(String[]a){
IntStream.range(1,1000000).filter(i->!IntStream.range(2,i).anyMatch(j->i%j==0)).forEach(System.out::println);
}}

Performance is not optimal, but code is well readable. For faster computation could be code extended to use parallel streams:

import java.util.stream.*;
class P{public static void main(String[]a){
IntStream.range(1,1000000).parallel().filter(i->!IntStream.range(2,i).anyMatch(j->i%j==0)).forEachOrdered(System.out::println);
}}

Answer 64

Java - 101 characters

Ungolfed version:

for(int i=3, j; i < 1000000; i++) {
    for(j = 2; j < i / 2; j++)
        if (i % j ==0)
            break;
    System.out.printf(i % j != 0 ? i + "%n" : "");
}

Golfed version:

for(int i=3,j;i<1000000;i++){for(j=2;j<i/2;j++)if(i%j==0)break;System.out.printf(i%j!=0?i+"%n":"");}

Answer 65

Perl6 - 47

for 1..10**6 {(1 x$_)~~/^(11+?)$0+$/ or say $_}

credit to Gowtham's perl solution

• 1000000 better written as 10**6
• print "$_\n" became say $_
• =~ became ~~
• needed to add whitespace in front of the x operator

Answer 66

Dart - 75 chars

Loop based version:

main(i,j){for(i=2;i<1e6;i++)l:{for(j=2;j<i;j++)if(i%j<1)break l;print(i);}}

It's much faster if you change j<i to j*j<=i, but not shorter!

Alternative List based version (107 chars) Not going to win any records without a shorter way to generate the list.

main(p,q){p=new List.generate(999998,(x)=>x+2);while(!p.isEmpty){print(q=p[0]);p.removeWhere((x)=>x%q<1);}}

Ungolfed

    main(p,q) { 
      p = new List.generate(999998, (x) => x + 2);
      while (!p.isEmpty) { 
        print(q = p[0]);
        p.removeWhere((x) => x%q < 1);
      }
    }

Answer 67

Bacchus, 34 bytes

\n[2..1E6]a(Öp:a(·=1.Öw)?),·¨

Explanation:

\n            Prepare the output to be one in each line

[2..1E6]      Generates an array from 2 to 1000000

:a            Push the array to the stack

(),·¨         For each element on the array we previously pushed to the stack

Öp:a          If current element of the for-each loop is Prime push 1 to the stack. Otherwise, push 0.

(·=1.Öw)?     If last pushed element is 1 then print current element of the for each loop.

Most of the code is used to output each prime in different lines. Otherwise a much shorter code (10 bytes) would be

[2..1E6]p#

Answer 68

LiveScript - 71 bytes

I was goofing around, trying to golf Sieve of Eratosthenes. I'm quite happy with the result. It uses prelude.ls.

x=1e6;[2 to x]|>unfoldr ([x]:l)->|l>[]=>[console.log<|x,l|>filter (%x)]

It outputs to the console. You can try the code in http://livescript.net - I recommend using lower limit than 1e6, because it gets slow at those numbers and probably hangs your browser for a while. I couldn't find a way to stop LS from inlining [2 to 1e6], so I had to creae a var for it.

Just for the sake of it, the original function I mangled the first one from:

p=->[2 to it]|>unfoldr ([x]:l)->|l>[]=>[x,l|>filter (%x)]

Answer 69

JS, 100 67 57

By xem and subzey

Execute this in the browser's console or nodeJS.

Short version: 57b. (it's very long to end: ~ 20 min)

for(i=1;1e6>++i;p&&console.log(i))for(p=j=i;j-->2;)p*=i%j

Faster version, 100b (ends in ~ 1 min)

p=[];for(i=2;1E6>i;i++)for(t=0,j=i;1E6>j;j+=i)t&&(p[j]=1),t=1;for(i=2;1E6>i;i++)p[i]||console.log(i)

Answer 70

Prolog - 129

Not a very short variant, but reasonably fast. A simple implementation of the Sieve of Eratosthenes.

:-initialization m.
F+S+X:-G is F,(G=<1e6,X=G;G<1e6,(G+S)+S+X).
m:-assert(i-1),2+1+I,\+i-I,write(I),nl,I*I+I+J,assert(i-J),1=0;!.

Invocation:

time swipl -qf ./prime.pl < /dev/null | wc -l

78498

real    0m3.646s
user    0m3.468s
sys     0m0.264s

Readable:

:- initialization(main).

between2(From, _, X) :-
    X is From,
    X =< 1000000.
between2(From, StepSize, X) :-
    Y is From,
    Y < 1000000,
    between2(Y + StepSize, StepSize, X).

main :-
    assert(stroke(1)), % shorter than ":-dynamic stroke/1."
    between2(2, 1, I),
    \+ stroke(I),
    write(I), nl,
    between2(I*I, I, J),
    assert(stroke(J)),
    fail.
main.

Answer 71

Perl, 75

map{my($a,$b)=($_,0);for(2..$a-1){$a%$_==0&&$b++}$b||print"$a\n"}(2..10**6)

Answer 72

Pyth - 14 12 chars

Fkr2^T6IqlPk1k

Thanks so much to @FryAmTheEggman for removing two chars from filter and ![1:] instead of ==1. As you probably can guess I learned Pyth literally yesterday. :)

jbf!tPTtU^T6

Omg I actually beat Mathematica builtins. Its very simple it just loops through 2 to a million and uses trick that prime numbers have one number in thier prime factorization which pyth happens to have a function for.

jb:    Join with \n as sperator
f:     filter by
!tPT:  not tail of prime factorization of loop variable(tail would be falsey if len 1 so then negate)
tU^T6:  filter through range 2-million

It does take a verrrrrry long time to run, but if you want to just see it run, you can change the 6 to a 2 for primes under hundred.

Answer 73

Jagl Alpha 1.2 - 14 bytes

Not competing, language is younger than question

1e6r{m}%{PZp}/

Prints on separate lines.

Answer 74

Ruby 37 32

(2..1e6).map{|x|p x if x.prime?}

Answer 75

T-SQL, 141

Assuming a resultset is valid output, here's code that works with SQL Server 2008 R2. It uses a table to store previously found primes. The table is initialized with 2, and all odd integers greater than that are checked against the contents of the table at the point in time of the check. Runtime and efficiency obviously were not concerns....

DECLARE @ INT=3SELECT 2 p INTO # l:IF NULL=ALL(SELECT 1FROM # WHERE @%p=0)INSERT # VALUES(@)SET @+=2IF @<1e6GOTO l SELECT p FROM # ORDER BY p

Answer 76

Sage, 28 bytes

for i in primes(1e6):print i

Try it online

Answer 77

Pyth, 9 bytes

V^T6IP_NN

Explanation:

V starts a for loop from 0 to the next number, keeping N as the value
T = 10 and so ^T6 = 10^6 = 1000000
I is if, P_N checks if N is prime and returns True or False based on the result.
The final N is just to print it.

I'm new to Pyth so it's likely not the best solution. Any suggestions are welcome!

Answer 78

Java 8, 100 97 92 bytes

o->{for(int i=1,n,j;i++<1e6;){for(n=i,j=2;j<n;n=n%j++<1?0:n);if(n>1)System.out.print(n);}}

-3 bytes by thanks to @Nevay.
-5 bytes by converting Java 7 to Java 8.

I know there are already a few other Java answers. I didn't knew which to choose to put the comment on with my golfed method, so I decided to post this separate answer. Not to mention it's slightly or a lot shorter than any of the other current Java answers so far.

Explanation:

Try it here.

o->{                          // Method with empty unused parameter and no return-type
  for(int i=1,n,j;            //  Initialize some integers
      i++<1e6;){              //  Loop (1) from 2 through 1,000,000 (exclusive)
    for(n=i,j=2;              //   Set some integers
        j<n;                  //   Inner loop (2) from 2 through `n` (exclusive)
      n=                      //    Change `n` to:
        n%j++<1?              //     If `n` is divisible by `j`:
         0                    //      Change `n` to 0 (which means it isn't a prime)
        :                     //     Else:
         n                    //      Leave `n` unchanged
    );                        //   End of inner loop (2)
    if(n>1)                   //   If `n` is larger than 1, which means it's a prime:
      System.out.println(n);  //    Print `n` + new-line
  }                           //  End of loop (1)
}                             // End of method

Answer 79

Ruby, 60 bytes

for n in 0..1e6
if('1'*n)!~/^1?$|^(11+?)\1+$/
puts n
end
end

see here for explanation

Answer 80

Haskell, 126 chars, Using Sieve of Eratosthenes

import Data.Set 
g i n m|i>n=[]|member i m=g(i+1)n m|1<2=i:g(i+1)n(fromList[i*i,i*i+i..n]`union`m)
main=print$g 2(10**6)empty

Run quite fast on my machine.

% ghc primeList1.hs -O
[1 of 1] Compiling Main             ( primeList1.hs, primeList1.o )
Linking primeList1 ...

% time ./primeList1 >/dev/null
./primeList1 > /dev/null  5.04s user 0.05s system 99% cpu 5.100 total

Answer 81

Ruby, 94 (optimized for speed, 2.655 secs)

(a=[*2..n=1e6]).each{|p|next if !p
break if p*p>n
(p*p).step(n,p){|m|a[m]=nil}}
puts a.compact

Ran in 2.655 seconds on my machine, which is pretty good considering how slow Ruby is.

Here's how I timed it:

t = Time.now

(a=[*2..n=1e6]).each{|p|next if !p
break if p*p>n
(p*p).step(n,p){|m|a[m]=nil}}
puts a.compact

puts Time.now - t

It takes a ridiculously long time to output to stdout, so I did sieve.rb > sieve.txt (on Windows).

Answer 82

Python 2 (PyPy), 86 bytes

for i in range(2,int(1e6)):
	if all([i%j!=0 for j in range(2,int(i**0.5)+1)]): print i

Try it online!

Answer 83

Stax, 7 bytes^CP437

ç►╪(Æ;Ç

Run and debug online!

Explanation

Uses the unpacked version to explain.

wi|6QVM<
w           loop
 i          loop index `i`
  |6        the `i`th prime
    Q       print and keep on stack
     VM<    while the printed number is less than one million

Answer 84

Pyt, 8 bytes

6ᴇřĐṗ*žÁ

Try it online!

Explanation:

6ᴇ            Push 1000000
ř             Push [1,2,...,999999,1000000]
Đ             Duplicate top of stack
ṗ             Is each element prime (pushes array of booleans)
*             Multiply top two on stack element-wise
ž             Remove all zeros
Á             Push contents of array onto stack
              Implicit print

Answer 85

Microscript II, 18 bytes

6E_s{ls1+v;(lP)}*h

Requires the latest version of the interpreter due to a bug in how the previous version handled addition with null values (although in retrospect it might work even in the previous version if you change ls1+ to 1sl+).

Approximate pseudocode translation:

x=0
Repeat 10⁶ times:
    x=x+1
    if x is prime:
        print x
End

Answer 86

(M)AWK - 104 103 100 98 97 87

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

---

Old:

The 'x' file:

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

The size:

$ wc -c x
97 x

The run (counting output lines instead of wasting space here) on a Thinkpad T60/T5500@1.6GHz in powersave mode (1 GHz clock, Debian6):

$ time mawk -f x | wc -l
78498

real    0m3.894s
user    0m3.820s
sys     0m0.072s

But since this won't be the shortest solution, speed is no matter.

The algorithm is a reorganized sieve method. I have not seen this method elsewhere up to now and the local name is "floating sieve of erathosthenes" (FSOE) until I know better.

Answer 87

Groovy - 65 chars

This feels like cheating, but... Output confirmed against other solutions (i.e. 'probable prime' is accurate for such small values)

n=new BigInteger(1);78498.times{println n=n.nextProbablePrime()}

The code uses the fact that there are 78498 primes that fit the requirement.

Answer 88

C# & LinqPad 71

As usual directly executable in LinqPad

for(int i=0;++i<1e6;){for(int b=1;++b<i;)if(i%b==0)goto a;i.Dump();a:;}

Takes about 7 minutes on my computer.

Answer 89

Perl, 35

use ntheory":all";print_primes(1e6)

Fast and small vs. the usual golf horrifically slow regex. I used this earlier for 39 characters:

use ntheory":all";say for@{primes(1e6)}

Answer 90

Golfscript, 55

{.2<{}{:l;1{).l\%}do}if}:r;10 6?,{..r={" "+print}{}if}%

Old code:

{:q-2:r\,{1+}%{q\%0={1r+:r}{}if}%;;r}:f 1000000,{f!},\;(;n*

WARNING. This program uses an extremely slow algorithm, it takes ~15 seconds for it to display the 1000 first primes and the time grows exponentially. If you want to use it, change the 1000000 in the code to something lower.

Answer 91

><> (Fish), 54 51 bytes

11+:aa*:\/&~!
:**=?;2&\
:v?=&:&:<^!?%&+1:&
.\:nao90

There's Befunge but no ><>, so I thought "might as well". Uses the ever so slow trial division.

Answer 92

Smalltalk - 22 characters

Integer primesUpTo:1e6

The dialect is Smalltalk/X; other dialects have the same or a similar method in Integer.

Exec. time (measured with: "Time millisecondsToRun:[...]" is 90ms on my somewhat older (2010) 2.6Ghz Mac.

Evaluating "(Integer primesUpTo:1e6) size" returns: 78498

Answer 93

Ruby, 118 117 bytes

n=999984;t=true;a=[t]*n;(2..Math.sqrt(n).round).each{|i|a[i]&&(i..n/i).each{|j|a[j*i]=!t}};(2..n).each{|i|a[i]&&p(i)}

Run Time:

0.53s user 0.13s system 92% cpu 0.714 total

Answer 94

C (111)

x=1000000,s[1000000],j;main(i){while(++i<x)for(j=2*i;j<x;j+=i)
s[j]=1;for(i=1;++i<x;)if(!s[i])printf("%d\n",i);}

C (112)

x=1000000,s[1000000],j;main(i){while(++i<x)for(j=2*i;j<x;j+=i)
s[j]=1;i=1;while(++i<x)if(!s[i])printf("%d\n",i);}

C (113, over 25% faster)

x=1000,s[1000000],j;main(i){while(++i<x)for(j=i*i;j<x*x;j+=i)
s[j]=1;i=1;while(++i<x*x)if(!s[i])printf("%d\n",i);}

C (ungolfed)

#include <stdio.h>
int sieve[1000000];
int main(void) {
    int i, j;
    for (i = 2; i < 1000; i++)
        for (j = i * i; j < 1000000; j += i)
            sieve[j] = 1;
    for (i = 2; i < 1000000; i++)
        if (!sieve[i])
            printf("%d\n", i);
    return 0;
}

Answer 95

Python, 68

print[a for a in range(2,999999)if all(a%b for b in range(2,a/2+1))]

Sadly, there's no hope in seeing it terminate within any reasonable time frame...

Answer 96

Swift 2, 79 bytes

Utilises the Sieve of Eratosthenes.

var r=[Int](2..<Int(1e6));while r.count>0{print(r[0]);r=r.filter{$0%r[0] != 0}}

Notes:

• Solution without the sieve needs two extra bytes.
• Takes ~14 mins on i5 3.5 GHz; or ~40 secs if compiled with optimisations.
• Use -O flag with swiftc to turn on optimisations.

Answer 97

Molecule (v6+), 19 bytes (non-competing)

0{1+_p?~}u1000000L

Explanation:

0{1+_p?~}u1000000L
0{1+_p?~}          Push 0, add a code block.
         u1000000  Push one million.
                 L Repeat the code block 1000000 times.

Answer 98

Oracle SQL 11.2, 139 bytes

WITH v AS(SELECT LEVEL i FROM DUAL CONNECT BY LEVEL<=:1)SELECT a.i FROM v a, v b GROUP BY a.i HAVING:1-2=SUM(SIGN(MOD(a.i,b.i)))ORDER BY 1;

Answer 99

Java 107 Bytes, 26 minutes, naive approach

y->{int i=1,j,n,r=0;for(j=2,n=1000000;(r+=++i>=j?1:0)!=n;j+=j%i==0?i=1:0)System.out.print(i>=j?j+"\n":"");}

ungolfed

                y->{
                int i=1,j,n,r=0;
                for(j=2,n=1000000; 
                    (r+=((++i>=j)?1:0))!=n; 
                    j+=((j%i==0)?i=1:0)) {
                    System.out.print(i>=j?j+"\n":"");
                }
                }

Worstcase Runtime is O(n) divisons for primes as it tests everything in [2,i[ and looks if anything divides i and prints it if it's divisorless or continues if a divisor is found. n*O(n) would make it O(n^2), but due to distribution of divisors and primes, it is something along O(n^2/log(n))+O(n*log(n)) divisons. In practice this takes something along 26 minutes apparently.

Java ungolfed 1601 Bytes, adaptive wheel sieve, 1.6 seconds

public class Sieve {
    ArrayList<Integer> primes = new ArrayList<>();
    ArrayList<Integer> candidates = new ArrayList<>();
    int target = Integer.MAX_VALUE;
    int product = 1;
    int nextEvolve = 0;
    int multiplier = 1;
    int iteration = 0;
    boolean evolve = true;
    Sieve(int n) {
        this.candidates.add(1);
        this.target = n;
    }
    int next() {
        final int toTest = this.product*this.multiplier+this.candidates.get(this.iteration);
        //System.out.println("try: "+toTest+" p:"+this.product+" m:"+this.multiplier+" i:"+this.iteration);
        for(int i = this.nextEvolve; i < this.primes.size() && toTest/this.primes.get(i)>=this.primes.get(i); ++i) {
            if(toTest%this.primes.get(i)==0) {
                ++this.iteration;
                if((this.iteration%=this.candidates.size())==0) {
                    ++this.multiplier;
                }
                return this.next();
            }
        }
        this.primes.add(toTest);
        ++this.iteration;
        if((this.iteration%=this.candidates.size())==0) {
            ++this.multiplier;
            if(this.evolve && this.multiplier%this.primes.get(this.nextEvolve)==0) {
                if(this.target/this.product<toTest) {
                    this.evolve = false;
                }else {
                    final int size = this.candidates.size();
                    for(int i = 1; i < this.primes.get(this.nextEvolve); i++) {
                        for(int j = 0; j < size; j++) {
                            if((i*this.product+this.candidates.get(j))%this.primes.get(this.nextEvolve)!=0) {
                                this.candidates.add(i*this.product+this.candidates.get(j));
                            }
                        }
                    }
                    this.product*=this.primes.get(this.nextEvolve);
                    this.multiplier=this.multiplier/this.primes.get(this.nextEvolve);
                    ++this.nextEvolve;
                }
            }
        }
        return toTest;
    }
    public static void main(String[] args) {
        try {
            System.in.read();
        } catch (final IOException e) {
            e.printStackTrace();
        }
        final Sieve s = new Sieve(1_000_000);
        for(int prime = s.next(); prime < 1_000_000; prime = s.next()) {
            System.out.println(prime);
        }
    }
}

Java golfed 883 Bytes, 16 seconds

class S{ArrayList<Integer> p=new ArrayList<>(),c=new ArrayList<>();int t,q,n,m,i;boolean e=true;S(int n){this.c.add(1);this.t=n;q=m=1;n=i=0;}int next(){int toTest=this.q*this.m+this.c.get(this.i);for(int i=this.n;i<this.p.size();++i)if(toTest%this.p.get(i)==0){++this.i;if((this.i%=this.c.size())==0)++this.m;return this.next();}this.p.add(toTest);++this.i;if((this.i%=this.c.size())==0){++this.m;if(this.e && this.m%this.p.get(this.n)==0){if(this.t/this.q<toTest) this.e=false;else{int size=this.c.size();for(int i=1;i<this.p.get(this.n);i++)for(int j=0;j<size;j++)if((i*this.q+this.c.get(j))%this.p.get(this.n)!=0)this.c.add(i*this.q+this.c.get(j));this.q*=this.p.get(this.n);this.m=this.m/this.p.get(this.n);++this.n;}}}return toTest;}public static void main(String[] args){S s=new S(1_000_000);for(int prime=s.next();prime<1_000_000;prime=s.next()){System.out.println(prime);}}}

Answer 100

Pyth, 9 bytes

V^T6IP_NN

Try it online!

Explanation:

V   : Iterate over all numbers from 0 to ...  
^T6 : 10^6
I   : If ...  
P_N : number is prime ...  
N   : print number

Answer 101

Vim, 34 bytes

6@=9<CR>o<Tab>0<Esc>V{g<C-A>dj=:g/\v^(<Tab><Tab>+)\1+</d<CR>

This is a direct adaptation of my top solution to Prime Numbers. The difference is... here I have to go up to a million. This forces a cool tactic to put 999999 into the readahead, but it also makes this solution impossible to run. You won't even get past the setup making the number array, because you'd need to fill more than half a terabyte of RAM (without overhead). And if you ever got to the regex algorithm... well, it sucks. You'd never finish.

This solution requires :set autoindent noexpandtab, which you might have set already, might not. It also requires computer hardware that doesn't exist.

• 6@=9<CR>: Cool trick to write 999999 in 5 bytes. Integer 9 gets evaluated into the expression register as text. That "macro" is run 6 times.
• o<Tab>0<Esc>: Make N (999,999) lines of zeroes, with stair-step indent. This is kind of like what happens when you paste in insert mode without doing :set paste.
• V{g<C-A>: Visual increment to turn the 0s into a list of numbers 1-999,999. Conveniently leaves cursor on top.
• dj: Remove the blank (zero) and 1 lines.
• =:: Vim users rarely think of the : command as an operator, but it is one (a charwise operator, surprisingly). Runs the = out to where the : command would move the cursor (top to bottom in this case).
• \v^(<Tab><Tab>+)\1+<: Regex that matches a composite number of tabs. If you haven't, watch the VimCast episode, which covers an old version of this solution. The :g//d will delete those lines. The cursor will end on the last remaining line, which will act as the operator for = to remove all indent.

Vim, 36 bytes (actually runs)

• 6@=9<CR>O0<Esc>V{g<C-A>:%norm~V$EkdYo@0D@.<C-O>@.<CR>d

This :normal macro is a proper sieve of Eratosthenes that cleans up after itself. I actually ran this out to 1,000,000. Took 10-15 minutes. The algorithm is quite good, but the data structure (array of lines in Vim) comes with a big toll. I wrote about it in more detail a long time ago.

Answer 102

Stata, 21 bytes

primes 1000000, clear

This is (obviously) a built-in command...

Answer 103

ASMD, 7 bytes (non-competing)

W(i|P?p

Explanation:

W        # Push 1,000,000
 (       # Begin range loop (0 -> 999,999)
  i      # Push counter variable
   |     # Duplicate
    P?p  # If prime, print
       . # Implicit end range loop