# 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

## Python 3, 45 bytes

k=P=1
while k<1e6:P%k>0==print(k);P*=k*k;k+=1


Try it online!

By the time the loop reaches testing k, it has iteratively computed the squared-factorial P=(k-1)!^2. If k is prime, then it doesn't appear in the product 1 * 2 * ... * (k-1), so it's not a factor of P. But, if it's composite, all its prime factors are smaller and so in the product. The squaring is only actually needed to stop k=4 from falsely being called prime.

More strongly, it follows from Wilson's Theorem that when k is prime, P%k equals 1. Though we only need that it's nonzero here, it's useful in general that P%k is an indicator variable for whether k is prime.

Thanks to @Sisyphus for 1 byte with P%k>0==print(k) using chained operator short-circuiting in place of P%k and print(k).

• You can save a byte doing P%k>0==print(k) instead of P%k and print(k). Oct 1, 2020 at 0:07
• @Sisyphus Great find, and on an answer that's had many eyes on it! Well worth an outgolfing bounty. Is there an answer of yours I can bounty for this? You could also post this improvement as an answer here, or post an answer here in another language.
– xnor
Oct 1, 2020 at 7:10
• I've posted a Julia answer, since I'd prefer the improvement stays in your (highly visible) post (and you did 99% of the work with Wilson's theorem!). Oct 1, 2020 at 7:27

### Mathematica, 17 24

Just for comparison:

Prime@Range@78498


As noted in a comment I failed to provide one prime per line; correction:

Column@Prime@Range@78498

• Prime~Array~78498 also 17 :) Nov 5, 2014 at 13:38
• Would be nine bytes in mthmca, if that were to be released. May 28, 2016 at 10:53
• That violates the condition of one prime per line of output. Prefixing with Print/@ and terminating with ; to prevent output of a long list of Nulls fixes that, at the cost of 8 extra characters. Jun 25, 2017 at 9:43
• @celtschk I don't know if I missed or disregarded that five years ago. Jun 25, 2017 at 19:11
• Well, I definitely missed that it was from five years ago :-) Jun 25, 2017 at 19:36

## C, 61 chars

Almost exactly the same as this one (the question is almost exactly the same too).

n=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:n%m?m-1:n++);}

• Got SEG-FAULT after printing 881 Jul 21, 2014 at 7:32
• @Manav, perhaps you compiled without optimizations. It relies on a good optimizer, which will remove the recursion. Jul 21, 2014 at 10:50
• Yes adding -O3 to gcc solved the problem!! Jul 21, 2014 at 11:23
• This method is insane. I love it. May 7, 2015 at 18:41
• I can get you to 57 bytes n=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:m-++n%m);} Oct 1, 2016 at 6:10

### MATLAB (16) (12)

Unfortunately, this outputs on a single line:

primes(1000000)


but that is solved by a simple matrix transpose:

primes(1000000)'


and I can cut out some characters by using exponential notation (as suggested in the comments):

primes(1e6)'

• Using 1e6 instead of 1000000 helps here too. May 14, 2014 at 18:53
• @orion That would make it 11 characters Oct 31, 2014 at 7:18
• @Axoren that does not include the ' at the end Mar 6, 2018 at 15:58

## Bash (37 chars)

seq 2 1e6|factor|sed 's/.*: //g;/ /d'


## (60 chars)

seq 2 1000000|factor|sed -e 's/[0-9]*: //g' -e '/^.* .*$/ d'  on my computer (2.0 GHz cpu, 2 GB ram) takes 14 seconds. • This can be improved to: seq 2 1000000|factor|sed 's/[0-9]*: //g;/^.* .*$/ d' May 26, 2012 at 9:13
• yes you're right. I wrote my sed command clean, not golfed :P May 26, 2012 at 9:15
• seq 1e6|factor|awk '$0=$2*!$3' is a bit shorter. Apr 2, 2014 at 23:23 • seq, factor and sed are external programs, this may as well be c p where c is a symlink to cat and p is a text file with primes up to a million... can you do it with shell builtins? May 13, 2014 at 16:28 • @technosaurus seq and factor are in coreutils, so it's legitimate. sed is also pretty ubiquitous. coreutils can be treated like a built-in. Bash without coreutils is like C++ without the STL. – user16402 May 13, 2014 at 16:32 ## J, 21 characters 1[\p:i.(_1 p:1000000)  which can be shortened to 1[\p:i.78498  if you know how many primes there are below 1000000. • Using enfile items, ,., instead of 1[\\ to save a character. Remove the unnecessary parenthesis, and use exponential notation: 1e6. – Omar Feb 17, 2015 at 19:49 • Came up with this: ,.i.&.(p:^:_1)1e6 Not shorter (after applying @Omar 's suggestions) but I found the use of under interesting. – kaoD Mar 27, 2017 at 17:25 # Bash, 30 bytes Since saeedn won't act on my suggestion – which is both shorter and faster than his approach – I thought I'd post my own answer: seq 1e6|factor|awk '$0=$2*!$3'


### How it works

seq 1e6


lists all positive integers up to 1,000,000.

factor


factors them one by one. For the first ten, the output is the following:

1:
2: 2
3: 3
4: 2 2
5: 5
6: 2 3
7: 7
8: 2 2 2
9: 3 3
10: 2 5


Finally,

awk '$0=$2*!$3'  changes the entire line ($0) to the product of the second field (the first prime factor) and the logical negation of the third field (1 if the is one prime factor or less, 0 otherwise).

This replaces lines corresponding to prime numbers with the number itself and all other lines with zeros. Since awk only prints truthy values, only prime number will get printed.

$p  # Bash, 37 Will golf more, if I can... Most of this is trying to parse factor's awkward output format. seq 1e6|factor|grep -oP "(?<=: )\d+$"


Takes 5.7 or so seconds to complete on my machine.

(It just happened that my post was the first to go on the second page of answers, so nobody is going to see it...)

## Old solution

This is longer and slower (takes 10 seconds).

seq 1e6|factor|egrep ':.\S+$'|grep -oE '\S+$'

• Wow - I never came across factor before, but there it is right there in coreutils! May 13, 2014 at 21:23
• Shave off one character: seq 1e6|factor|grep -oP "(?<=: )\d+$" with a perl-grep lookbehind May 13, 2014 at 21:35 • @DigitalTrauma how does that work – user16402 May 14, 2014 at 7:24 • -P enables perl-style regexes. (?<=: ) is a positive lookbehind for the string ": ". Basically this says that ": " must come before what matches \d+$, but is not actually part of the match, so the -o option just gives us one matching number after the colon, i.e. just gives numbers where there is only one factor, i.e. prime. May 14, 2014 at 16:21
– user16402
May 14, 2014 at 16:34

# Python 3.x: 66 chars

for k in range(2,10**6):
if all(k%f for f in range(2,k)):print(k)


# More efficient solution: 87 chars

Based on the Sieve of Eratosthenes.

p=[];z=range(2,10**6)
while z:f=z[0];p+=[f];z=[k for k in z if k%f]
for k in p:print(k)


mapM print [n|n<-[2..10^6],all((>0).rem n)[2..n-1]]

• You can change mapM_ to mapM, return value won't be printed, and this is Code Golf. ;) Oct 31, 2013 at 10:58
• why are there extra spaces after print and in (> 0)? Aug 4, 2014 at 2:52
• You can replace 999999 with 10^6. And please update your byte count - 63 can't possibly be right. Jul 29, 2015 at 22:21

### Ruby 50 41

require'mathn'
p (2..1e6).select &:prime?

• No need for .to_a, as Enumerable already includes select. You can also use the shorthand notation for Symbol#to_proc to shorten it further: p (2..1e6).select &:prime? (1 is not prime) May 26, 2012 at 19:41
• @Ventero thanks a lot! I didn't know about the Symbol#to_proc. I gotta pay more attention to the shortcuts Ruby offers. May 26, 2012 at 19:53
• Shorter version require'prime';p Prime.take 78498. Nov 25, 2013 at 10:46
• @ŁukaszNiemier Great! I think that's so different that you can post it as a separate answer. Nov 25, 2013 at 14:08
• Good use of some good ol' country boy mathn' Apr 27, 2016 at 20:22

# Julia, 11

primes(10^6)


It looks like built ins are getting upvotes, plus I needed more words for longer answer.

## APL, 15

p~,p∘.×p←1↓⍳1e6


My interpreter ran into memory problems, but it works in theory.

• How? Can you give a deskription? Aug 31, 2015 at 20:39
• You need a ⍪ in front to make one number per line, and you don't need the ,.
Sep 3, 2015 at 8:18
• @RasmusDamgaardNielsen ⍳ are the first integers. 1↓ drops the first one. p← assigns to p. p∘.×p makes a multiplication table. p~ removes from p whatever is on the right. (, isn't needed, it ravels the table into a list.)
Sep 3, 2015 at 8:21

# Perl, 49 bytes

Regular expression kung fu :)

for(1..1E6){(1x$_)=~/^(11+?)\1+$/ or print"$_\n"}  Ungolfed version: for(1 .. 1_000_000) { (1x$_) =~ /^(11+?)\1+$/ or print "$_\n";
}


It hasn't even made 10% progress while I type this post!

Source for the regex: http://montreal.pm.org/tech/neil_kandalgaonkar.shtml

• inspired me to write a perl6 version. also, 1000000 can be written 10**6
– pabo
Aug 4, 2014 at 22:17
• Also, 1000000 can be written 1E6
– mob
May 7, 2015 at 21:02
• Always was a favorite regex of mine, but you need to remember that it fails spectacularly once you get to higher numbers - because of the fact that it's converting huge numbers into unary. This regex might not work for finding primes in the hundreds of thousands and beyond, depending on one's configuration of the language (and your machine.) Oct 3, 2015 at 18:10

# J (15 or 9)

I can't believe this beat Mathematica (even if it's just a single by 2 chars)

a#~1 p:a=:i.1e6


Or:

p:i.78498

• ... The output format should be one number per line of output. That's why my answer begins with 1[\ . May 15, 2014 at 8:05

# gs2, 5 bytes

Encoded in CP437:

∟)◄lT


1C 29 pushes a million, 11 6C is primes below, 54 is show lines.

## C, 91888582818076 72 characters

main(i,j,b){for(;i++<1e6;b++&&printf("%d\n",i))for(j=2;j<i;)b=i%j++&&b;}


The algorithm is terribly inefficient, but since we're doing code-golf that shouldn't matter.

• you can shorten it easily: main(i,j,b){for(;i++<1e6;b++&&printf("%d\n",i))for(j=2;j<i;)b=i%j++&&b;} or some idea like this (since I actually didn't compile it) May 27, 2012 at 11:34
• How is i sure to be 0? I think that, if you provide any argument, it'll fail. Also, I think j will have some sort of type error. Not sure for b though. Jul 17, 2016 at 21:57

# GolfScript, 22/20 (20/19) bytes

n(6?,:|2>{(.p|%-.}do:n


At the cost of speed, the code can be made two bytes shorter:

n(6?,:|2>.{|%2>-}/n*


If the output format specified in the edited question is disregarded (which is what many of the existing answers do), two bytes can be saved in the fast version and one can be saved in the slow one:

n(6?,:|2>{(.p|%-.}do
n(6?,:|2>.{|%2>-}/


This will print an additional LF after the primes for the fast version, and it will print the primes as an array for the slow one.

### How it works

Both versions are implementations of the sieve of Eratosthenes.

The fast version does the following:

1. Set A = [ 2 3 4 … 999,999 ] and | = [ 0 1 2 … 999,999 ].

2. Set N = A[0] and print N.

3. Collect every N-th element from | in C. These are the multiples of N.

4. Set A = A - C.

5. If A is non-empty, go back to 2.

n(6?   # Push "\n".pop() ** 6 = 1,000,000.
,:|    # Push | = [ 0 1 2 … 999,999 ].
,2>    # Push A = [ 2 3 4 … 999,999 ].
{      #
(    # Unshift the first element (“N”) of “A”.
.p   # Print “N”.
|%   # Collect every N-th element from “A” into a new array, starting with the first.
-    # Take the set difference of “A” and the array from above.
.    # Duplicate the set difference.
}do    # If the set difference is non-empty, repeat.
:n     # Store the empty string in “n”, so no final LF will get printed.


The slow version works in a similar fashion, but instead of successively removing multiples of the minimum of “A” (which is always prime), it removes multiples of all positive integers below 1,000,000.

### Competitiveness

In absence of any built-in mathematical functions to factorize or check for primality, all GolfScript solutions will either be very large or very inefficient.

While still far from being efficient, I think I have achieved a decent speed-to-size ratio. At the time of its submission, this approach seems to be the shortest of those that do not use any of the aforementioned built-ins. I say seems because I have no idea how some of the answers work...

I've benchmarked all four submitted GolfScript solutions: w0lf's (trial division), my other answer (Wilson's theorem) and the two of this answer. These were the results:

Bound     | Trial division     | Sieve (slow)       | Wilson's theorem | Sieve (fast)
----------+--------------------+--------------------+------------------+----------------
1,000     | 2.47 s             | 0.06 s             | 0.03 s           | 0.03 s
10,000    | 246.06 s (4.1 m)   | 1.49 s             | 0.38 s           | 0.14 s
20,000    | 1006.83 s (16.8 m) | 5.22 s             | 1.41 s           | 0.38 s
100,000   | ~ 7 h (estimated)  | 104.65 (1.7 m)     | 35.20 s          | 5.82 s
1,000,000 | ~ 29 d (estimated) | 111136.97s (3.1 h) | 3695.92 s (1 h)  | 418.24 s (7 m)

• Is the "slow" sieve just a Sieve of Eratosthenes? May 27, 2016 at 0:15
• Both are. The slow version is just an awful implementation. May 27, 2016 at 0:17

# NARS2000 APL, 7 characters

⍸0π⍳1e6

• Welcome to Programming Puzzles & Code Golf! Sep 26, 2015 at 14:29

## Golfscript 26 25 24

### Edit (saved one more char thanks to Peter Taylor):

10 6?,{:x,{)x\%!},,2=},


Old code:

10 6?,{.,{)\.@%!},,2=*},


This code has only theoretical value, as it is incredibly slow and inefficient. I think it could take hours to run.

If you wish to test it, try for example only the primes up to 100:

10 2?,{:x,{)x\%!},,2=},

• You can save a character by replacing \; with *. (You can also get much faster for the current character count by finding the first divisor rather than all of them: 10 6?,2>{.),2>{1$\%!}?=}, May 26, 2012 at 23:05 • @PeterTaylor Thanks, using multiplication there is a very neat trick. May 27, 2012 at 9:42 • There's one more char saving with a variable: replace ., with :x, and \.@ with x\  (whitespace is because of escaping issues with MD in comments) and remove *. Apr 1, 2014 at 15:10 • @PeterTaylor good one, thanks! I've edited my code. Apr 1, 2014 at 15:34 # CJam - 11 1e6,{mp},N*  1e6, - array of 0 ... 999999 {mp}, - select primes N* - join with newlines • Isn't CJam more recent than this question? Jul 14, 2014 at 13:21 • @PeterTaylor oh, yes it is Jul 14, 2014 at 14:23 # GolfScript, 25 (24) bytes !10 6?,2>{.(@*.)@%!},n*\;  If the output format specified in the edited question is disregarded, one byte can be saved: !10 6?,2>{.(@*.)@%!},\;  This will print the primes as an array (like many other solutions do) rather than one per line. ### How it works The general idea is to use Wilson's theorem, which states that n > 1 is prime if and only if ! # Push the logical NOT of the empty string (1). This is an accumulator. 10 6? # Push 10**6 = 1,000,000. ,2> # Push [ 2 3 4 … 999,999 ]. { # For each “N” in this array: .( # Push “N - 1”. @ # Rotate the accumulator on top of the stack. * # Multiply it with “N - 1”. The accumulator now hold “(N - 1)!”. .) # Push “(N - 1)! + 1” @ # Rotate “N” on top of the stack. %! # Push the logical NOT of “((N - 1)! + 1) % N”. }, # Collect all “N” for which “((N - 1)! + 1) % N == 0” in an array. n* # Join that array by LF. \; # Discard the accumulator.  ### Benchmarks Faster than trial division, but slower than the sieve of Eratosthenes. See my other answer. # Java, 110 bytes void x(){for(int i=1;i++<1e6;)System.out.print(new String(new char[i]).matches(".?|(..+?)\\1+")?"":(i+"\n"));} Using unary division through regex as a primality test. # 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. # Mathematica 25 Assuming you don't know the number of primes less than 10^6: Prime@Range@PrimePi[10^6]  # J, 16 chars 1]\(#~1&p:)i.1e6  Without the output format requirement, this can be reduced to 13 chars: (#~1&p:)i.1e6  1]\ just takes the rank 1 array of primes, turns it into a rank 2 array, and puts each prime on its own row -- and so the interpreter's default output format turns the one line list into one prime per line. (#~ f) y is basically filter, where f returns a boolean for each element in y. i.1e6 is the range of integers [0,1000000), and 1&p: is a boolean function that returns 1 for primes. ## R, 45 43 characters for(i in 2:1e6)if(sum(!i%%2:i)<2)cat(i," ")  For each number x from 2 to 1e6, simply output it if the number of x mod 2 to x that are equal to 0 is less than 2. • The first number produced by this code is 1, but 1 is not a prime. Nov 17, 2013 at 18:32 # Bash (433643) My (not so clever) attempt was to use factor to factor the product. factor${PRODUCT}


Unfortunately with large numbers the product is of course huge. It also took over 12 hours to run. I decided to post it though because I thought it was unique.

Here is the full code.

If it was primes under six it would be reasonable.

  factor 30


Oh well, I tried.

• +1 This answer is truly diabolical. Not quite precomputed result (it saves quite a bit of characters), and much much more terrible to compute :) It's quite possibly also an example that makes the optimized factor perform much worse than the basic trial division algorithm. May 15, 2014 at 6:59