List of primes under a million

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.

• It's not an exact duplicate, but it is essentially just primality testing, which is a component of a number of existing questions (e.g. codegolf.stackexchange.com/questions/113, codegolf.stackexchange.com/questions/5087 , codegolf.stackexchange.com/questions/1977 ). FWIW, one guideline which isn't followed enough (even by people who should know better) is to pre-propose a question in the meta sandbox meta.codegolf.stackexchange.com/questions/423 for criticism and discussion of how it can be improved before people start answering it. – Peter Taylor May 26 '12 at 8:42
• Ah, yes, I was worried about this question being too similar to the plethora of prime number-related questions already around. – Delan Azabani May 26 '12 at 8:44
• @GlennRanders-Pehrson Because 10^6 is even shorter ;) – ɐɔıʇǝɥʇuʎs May 14 '14 at 5:20
• A few years back I submitted an IOCCC entry that prints primes with only 68 characters in C -- unfortunately it stops well short of a million, but it might be of interest to some: computronium.org/ioccc.html – Computronium Jun 25 '17 at 21:45
• @ɐɔıʇǝɥʇuʎs How about 1e6 :-D – Titus Mar 3 '18 at 2:09

NARS2000 APL - 9 characters

¯2π⍳2π1e6


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

• This is sinister black magic. – user16402 May 13 '14 at 18:40
• @professorfish I assume I should add an explanation? – Oberon May 13 '14 at 18:41
• yessssssss (putting in extra sssss because of char limit_) – user16402 May 13 '14 at 18:42
• You need ⍪ for the proper output (and btw, ¯2π⍳78498 is much simpler). – Adám Jun 28 '16 at 20:05

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

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.

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")


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.

• quite a big variety of speeds here, one of my answers took 4.5 seconds – user16402 May 14 '14 at 16:38

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

• Giving last prime number can save one character. – Prince John Wesley May 27 '12 at 13:28

Octave, 12, 11

primes(1e6)


Write 1000000 as 1e6

• 1e6 is even shorter ;) – jpjacobs Oct 30 '13 at 13:31
• Editted in. Thanks for the info :) – MrD Oct 30 '13 at 21:17

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++;);


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#^        #<^#<@


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.

• I think that should be INT(I/J) not I/I. Btw. that´s 56 bytes; and 56 characters (the last line needs a RETURN as well so it gets recognized). 1F┌I=2TO10^6:F┌J=2TOI/2:IF(I/J!=INT(I/I))N─:?I and 2N─I is four characters shorter and six bytes smaller. Nice approach though. – Titus Mar 3 '18 at 12:31
• Oh and for those that think that integer varibales would be faster: They´re not. Commodore Basic transforms integer values to float for calculations. – Titus Mar 3 '18 at 12:38

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]));


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)

• You can save a byte by incrementing in the compare for(i=1,l=[];++i<1e6;) – andrewarchi Jun 14 '17 at 17:01

MATL, 5 bytes

1e6Zq


Explanation:

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


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

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)

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.

• Welcome to PPCG! – Martin Ender Jun 25 '17 at 21:16
• I improved the formatting and added in a Try It Online link. Also 5 bytes – caird coinheringaahing Dec 9 '17 at 12:34
• @cairdcoinheringaahing not sure if it was in the syntax at the time, but you could replace 10*6 with ȷ6 to save a byte. – Nick Kennedy Jun 15 '19 at 8:21

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. 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 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!) 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  • You can save a byte changing ε, to » (join by newlines; after which the result is implicitly output). – Kevin Cruijssen Nov 9 '18 at 14:47 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. Haskell, 65 chars main=print[x|x<-[2..999999::Int],null[i|i<-[2..x-1],mod x i==0]]  • Nice. Could you save a few by removing the ::Int ? – brander Mar 2 '17 at 4:08 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’

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);
}
}


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#