# 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

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


## JS, 10067 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)


# 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


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


# Perl, 75

map{my($a,$b)=($_,0);for(2..$a-1){$a%$_==0&&$b++}$b||print"$a\n"}(2..10**6)  # Jagl Alpha 1.2 - 14 bytes Not competing, language is younger than question 1e6r{m}%{PZp}/  Prints on separate lines. • Is this language younger than the question? – trichoplax Dec 30 '14 at 0:27 • Yes, I am not competing. Clarified in the answer @githubphagocyte – globby Dec 30 '14 at 0:27 • @githubphagocyte :) – globby Dec 30 '14 at 0:33 # 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. • Using pyth's filter function is a tad shorter: jbf!tPTtU^T6. This also saves a char by checking len(prime_factors(n)[1:])>0, which could also be added to your code: I!tPk. (This works because an empty list is False, and a list of any other length is True) Good luck with Pyth ;) – FryAmTheEggman Dec 30 '14 at 5:33 Ruby 37 32 (2..1e6).map{|x|p x if x.prime?}  • yeah that makes so much sense. THanks :) – shivam Mar 9 '15 at 12:35 • Actually, I can't find any documentation of prime?. Have you tested this? – Martin Ender Mar 9 '15 at 12:38 • yeah it works great. Here: ruby-doc.org/stdlib-1.9.3/libdoc/prime/rdoc/… – shivam Mar 9 '15 at 12:40 • This only works if the Prime module is loaded. You need to require 'prime' otherwise you get NoMethodError: undefined method prime?' for 2:Fixnum – daniero Sep 3 '15 at 17:38 ## 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  ## Sage, 28 bytes for i in primes(1e6):print i  Try it online • @FryAmTheEggman It's Python 2 – user45941 Apr 27 '16 at 19:05 # 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! # 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.

### 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 • Can you remove the space between for($i=0;$i<=1e6;$i++) and everything else? – CalculatorFeline Mar 2 '17 at 15:15
• @CalculatorFeline yep, thanks! – ʰᵈˑ Mar 2 '17 at 15:47
• Great algorithm! 28 bytes shorter: while(++$i<1e6)preg_match('/^1?$|^(11+?)\1+$/',$s.=1)||print"$i\n"; (not tested). Save one more byte with a literal newline. Have you tried ereg instead of preg_match? That would save another 8 bytes, shrinking your solution to 58 bytes. – Titus Mar 3 '18 at 2:18 # 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  ## 05AB1E, 7 bytes Since there is not yet an answer in 05AB1E. T6mGNp–  Try it online! • Why is the input for this 22? – Magic Octopus Urn Jun 14 '17 at 16:56 • @carusocomputing There is no reason for that... removed it – kalsowerus Jun 15 '17 at 5:49 # Java 8, 10097 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  • You can use if(n>1)System.out.println(n); instead of System.out.print(n>1?n+"\n":""); to save 3 bytes. – Nevay Aug 11 '17 at 12:39 # 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) • Welcome to PPCG! – Martin Ender Aug 12 '17 at 9:59 # 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 • You can save a byte (or two) and get it to not time out on tio: 6ᴇřĐṗ*žÁ. The Á is only to make the output match the format specified in the question, and can be removed if the output can be an array. – mudkip201 Mar 4 '18 at 14:28 • I feel like that's different enough to post as your own answer, but if you don't want to, I'll update. – RaviRavioli Mar 4 '18 at 20:56 • I'll post it as a separate answer – mudkip201 Mar 4 '18 at 20: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 ) # 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

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

• 102 – ASCII-only Apr 1 '19 at 5:32
• 100 – ASCII-only Apr 1 '19 at 5:52
• 94 - note my previous bytecounts should be 2 longer since i lowered loop limit – ASCII-only Apr 1 '19 at 5:57
• 88 – ASCII-only Apr 1 '19 at 6:01

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

# 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; – Peter Taylor May 26 '12 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? – Delan Azabani May 26 '12 at 8:54
• Fair point. One big improvement still possible, though: use a single loop. Can't think how I missed it earlier. – Peter Taylor May 26 '12 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. – Delan Azabani May 26 '12 at 9:42
• Sure it's possible. The part of the sieve up to i is complete. – Peter Taylor May 26 '12 at 10:59

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

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

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


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

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

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.

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

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.

# 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

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