# 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. May 26, 2012 at 8:42
• Ah, yes, I was worried about this question being too similar to the plethora of prime number-related questions already around. May 26, 2012 at 8:44
• @GlennRanders-Pehrson Because 10^6 is even shorter ;) May 14, 2014 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 Jun 25, 2017 at 21:45
• @ɐɔıʇǝɥʇuʎs How about 1e6 :-D Mar 3, 2018 at 2:09

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


# 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!)

## 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 +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, 2014 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. May 27, 2012 at 13:28

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 ? Mar 2, 2017 at 4:08

# Octave, 12, 11

primes(1e6)


Write 1000000 as 1e6

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

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

• There are several reasons why this is wrong. (1) You cannot implicitly convert from a double 1e6 to an int, but int is required by Range. (2) The inner Range must take at most n-2 terms, otherwise you will test n % n which is clearly 0. (3) You write x%n when you want n%x. Fixing these issues, something like this will work: Enumerable.Range(2,999999).Where(n=>Enumerable.Range(2,n-2).All(x=>n%x!=0)) However, this still does not output the numbers; the requirement was one per line. May 29, 2019 at 22:39

# 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. Mar 3, 2018 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. Mar 3, 2018 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;) Jun 14, 2017 at 17:01

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

• 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. # 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! Jun 25, 2017 at 21:16 • I improved the formatting and added in a Try It Online link. Also 5 bytes Dec 9, 2017 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. Jun 15, 2019 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,
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

# 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). Nov 9, 2018 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.

# Julia 1.x, 38 bytes

2:1e6 .|>i->0∉i.%(2:i-1)==println(i)


Try it online!

Since the other Julia answer 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.

# Vyxal, 4 bytes

k4'æ


Try it Online!

k4   # 1m
'  # 1...^ filtered by
æ # is prime?


# 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


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

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


# Matlab (12)

Pretty simple=)

primes(1e6)'

• So simple that there is already codegolf.stackexchange.com/a/6274/21348 Aug 3, 2014 at 16:48
• Oh, didn't see that one, but I have to say that mine is way shorter=) Aug 3, 2014 at 17:19

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

• I think you can remove some of the newlines. Jun 26, 2017 at 22:52

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

• @Martin Büttner Oups. Fixed it. Aug 4, 2014 at 21:20
• IDK, if that is an accepted format in Codegolf, you have to wrap it into a function, a lambda or a program. It helps other people to test your code faster and gives everyone using the same language a fair playing ground. May 26, 2016 at 14:13