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

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 2

Bashscript (41 chars)

seq 2 1000000|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 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

Ruby 50 41

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

Answer 5

F#, 100 chars 94

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 6

Golfscript 26 25

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?,{.,{)\.@%!},,2=*},`

Answer 7

Mathematica, 17

Just for comparison:

Prime@Range@78498

Answer 8

MATLAB (16)

Unfortunately, this outputs on a single line:

primes(1000000)

but that is solved by a simple matrix transpose:

primes(1000000)'

Answer 9

Python 3.x: 62 chars

for k in range(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 10

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 11

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 12

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 13

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 14

PowerShell 52

Extremely inefficient, but the shortest I could come up with.

$p=2..999998;$p|%{$n=$_;$p=$p|?{$_-le$n-or$_%$n}};$p

PowerShell 126

This is much faster; far from optimal, but a good compromise between efficiency and brevity.

 $p=2..999998;$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 15

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 16

QBASIC 75 CHARS

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.