# 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

# Matlab (12)

Pretty simple=)

primes(1e6)'

• So simple that there is already codegolf.stackexchange.com/a/6274/21348 Commented Aug 3, 2014 at 16:48
• Oh, didn't see that one, but I have to say that mine is way shorter=) Commented 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. Commented 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. Commented 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. Commented May 26, 2016 at 14:13

# Perl6 - 47

for 1..10**6 {(1 x$_)~~/^(11+?)$0+$/ or say$_}


credit to Gowtham's perl solution

• 1000000 better written as 10**6
• print "$_\n" became say$_
• =~ became ~~
• needed to add whitespace in front of the x operator
• you can use superscript version of 106 > 10⁶ so you can shorten range from 1..106 to ^10⁶ + you can move the for on the right side and it becomes 41 chars (1 x$_)~~/^(11+?)$0+$/ or say$_ for ^10⁶ Commented Jun 15, 2017 at 7:00
• You could also use .say instead of say $_. – bb94 Commented Apr 19, 2019 at 3:56 ## 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#  ## 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  Readable: :- 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? Commented Dec 30, 2014 at 0:27
• Yes, I am not competing. Clarified in the answer @githubphagocyte Commented Dec 30, 2014 at 0:27
• @githubphagocyte :) Commented Dec 30, 2014 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 ;) Commented Dec 30, 2014 at 5:33

Ruby 37 32

(2..1e6).map{|x|p x if x.prime?}

• yeah that makes so much sense. THanks :) Commented Mar 9, 2015 at 12:35
• Actually, I can't find any documentation of prime?. Have you tested this? Commented Mar 9, 2015 at 12:38
• yeah it works great. Here: ruby-doc.org/stdlib-1.9.3/libdoc/prime/rdoc/… Commented Mar 9, 2015 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 Commented Sep 3, 2015 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
Commented Apr 27, 2016 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!

### 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? Commented Mar 2, 2017 at 15:15
• @CalculatorFeline yep, thanks!
– ʰᵈˑ
Commented Mar 2, 2017 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. Commented Mar 3, 2018 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? Commented Jun 14, 2017 at 16:56 • @carusocomputing There is no reason for that... removed it Commented Jun 15, 2017 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. Commented Aug 11, 2017 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! Commented Aug 12, 2017 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. Commented Mar 4, 2018 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. – qqq Commented Mar 4, 2018 at 20:56 • I'll post it as a separate answer Commented Mar 4, 2018 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 ) • 59 bytes Commented Apr 1, 2019 at 3:12 # Pyt, 8 bytes 6ᴇřĐṗ*žÁ  Try it online! Explanation: 6ᴇ Push 1000000 ř Push [1,2,...,999999,1000000] Đ Duplicate top of stack ṗ Is each element prime (pushes array of booleans) * Multiply top two on stack element-wise ž Remove all zeros Á Push contents of array onto stack Implicit print  # 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

My still not golfed answer:

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 Commented Apr 1, 2019 at 5:32
• 100 Commented Apr 1, 2019 at 5:52
• 94 - note my previous bytecounts should be 2 longer since i lowered loop limit Commented Apr 1, 2019 at 5:57
• 88 Commented Apr 1, 2019 at 6:01

# Rockstar, 128 bytes

X's1
while X-999999
let X be+1
let D be X
P's1
while P and D-2
let D be-1
let M be X/D
turn up M
let P be X/D aint M

if P say X


Try it here (Code will need to be pasted in) - Extremely inefficient; knock a few 9s off the second line to have it complete in a sane amount of time.

# Factor + math.primes, 22 bytes

1e6 primes-upto stack.


Try it online!

• 1e6 primes-upto Get a list of primes up to a million
• stack. Prettyprint each element of a sequence, one per line

# C (gcc), 59 bytes

i;main(n){for(;n<1e6;i||printf("%d ",n))for(i=n++;n%i--;);}


Try it online! (upto 1000)

# CellTail, 165 bytes

I=-1;O=N;N,-1,N:N,(1,1,1),N;999999..,N,N:N,N,N;A,(a,a,b),N:N,a,a+1;A,(a,b,0),N:N,(a+1,2),N;A,(a,b),N:N,(a,b,a%b),N;A,(a,b,c),N:N,(a,b+1,a%(b+1)),N;a,N,N:N,(a,1,a),N;


Should eventually produce the correct output, will take a very long time though.

Try it online

Try it online, numbers up to 1000 so it will actually complete in a few minutes

# Arturo, 34 bytes

loop 1..1e6=>[if prime?<=&->print]
`

Try it