# 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. Commented 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. Commented May 26, 2012 at 8:44
• @GlennRanders-Pehrson Because 10^6 is even shorter ;) Commented 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 Commented Jun 25, 2017 at 21:45
• @ɐɔıʇǝɥʇuʎs How about 1e6 :-D Commented Mar 3, 2018 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
Commented May 13, 2014 at 18:40
• @professorfish I assume I should add an explanation? Commented May 13, 2014 at 18:41
• yessssssss (putting in extra sssss because of char limit_)
– user16402
Commented May 13, 2014 at 18:42
• You need ⍪ for the proper output (and btw, ¯2π⍳78498 is much simpler).
Commented Jun 28, 2016 at 20:05

# 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. Commented 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. Commented Mar 3, 2018 at 12:38

# 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

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

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

# Octave, 12, 11

primes(1e6)


Write 1000000 as 1e6

• 1e6 is even shorter ;) Commented Oct 30, 2013 at 13:31

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


## 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;) Commented Jun 14, 2017 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

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

# 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

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

# Vyxal, 4 bytes

k4'æ


Try it Online!

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


# Japt-R, 6 bytes

L³õ fj


Test it

L³õ fj
L          :100
³         :Cubed
õ        :Range [1,L³]
f      :Filter
j     :  Prime


# ThunnoN, $$\ 4 \log_{256}(96) \approx \$$ 3.29 bytes

Z6gN


Attempt This Online!

Note: this is very slow (it times out on ATO), so here's a version which prints the primes up to 1000: Attempt This Online!

Explanation:

Z6    # Push 10**6 (1000000)
g   # Filter (range of ^) for:
N  #  Primes
# N flag joins by newlines
# Implicit output


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

• i=1;while(++i<E) can be improved to for(i=1;++i<E;). for(j=2*i;j<x;j+=i)s[j]=1; can be improved to for(j=1;++j<x;)s[j*i]=1; Commented May 26, 2012 at 8:48
• Thanks. For your second improvement, though, considering that j would no longer be a direct index to the sieve, wouldn't comparing against x cause the program to significantly overrun the array? Commented May 26, 2012 at 8:54
• Fair point. One big improvement still possible, though: use a single loop. Can't think how I missed it earlier. Commented May 26, 2012 at 9:40
• As in, using one loop in total, or replacing the first pair of loops with one loop, resulting in two loops? I don't think the former is possible, as it'd mean printing while the sieve is in an incomplete state. Commented May 26, 2012 at 9:42
• Sure it's possible. The part of the sieve up to i is complete. Commented May 26, 2012 at 10:59

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