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 '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. May 26 '12 at 8:44
• @GlennRanders-Pehrson Because 10^6 is even shorter ;) 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 Jun 25 '17 at 21:45
• @ɐɔıʇǝɥʇuʎs How about 1e6 :-D Mar 3 '18 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 '20 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 '20 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 '20 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 '14 at 13:38
• Would be nine bytes in mthmca, if that were to be released. May 28 '16 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 '17 at 9:43
• @celtschk I don't know if I missed or disregarded that five years ago. Jun 25 '17 at 19:11
• Well, I definitely missed that it was from five years ago :-) Jun 25 '17 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 '14 at 7:32
• @Manav, perhaps you compiled without optimizations. It relies on a good optimizer, which will remove the recursion. Jul 21 '14 at 10:50
• Yes adding -O3 to gcc solved the problem!! Jul 21 '14 at 11:23
• This method is insane. I love it. May 7 '15 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 '16 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 '14 at 18:53
• @orion That would make it 11 characters Oct 31 '14 at 7:18
• @Axoren that does not include the ' at the end Mar 6 '18 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 '12 at 9:13
• yes you're right. I wrote my sed command clean, not golfed :P May 26 '12 at 9:15
• seq 1e6|factor|awk '$0=$2*!$3' is a bit shorter. Apr 2 '14 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 '14 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 '14 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 '15 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 '17 at 17:25 Ruby 34 require'prime';p Prime.take 78498 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 '14 at 21:23
• Shave off one character: seq 1e6|factor|grep -oP "(?<=: )\d+$" with a perl-grep lookbehind May 13 '14 at 21:35 • @DigitalTrauma how does that work – user16402 May 14 '14 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 '14 at 16:21
– user16402
May 14 '14 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;p+=[f];z=[k for k in z if k%f]
for k in p:print(k)
• The first one erroneously prints 0 and 1. You can fix this by instead using range(2,10**6). Also, I think the if statement has to be on a separate line from the out for or you get an error.
– xnor
May 13 '14 at 20:52
• @xnor: Fixed it. Aug 3 '14 at 20:15

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 '13 at 10:58
• why are there extra spaces after print and in (> 0)? Aug 4 '14 at 2:52
• nice catch! thanks Aug 4 '14 at 3:00
• You can replace 999999 with 10^6. And please update your byte count - 63 can't possibly be right. Jul 29 '15 at 22:21
• @user2845840 ok thanks. good idea! Jul 30 '15 at 0:47

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 '12 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 '12 at 19:53
• Shorter version require'prime';p Prime.take 78498. Nov 25 '13 at 10:46
• @ŁukaszNiemier Great! I think that's so different that you can post it as a separate answer. Nov 25 '13 at 14:08
• Good use of some good ol' country boy mathn' Apr 27 '16 at 20:22

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 '15 at 20:39
• You need a in front to make one number per line, and you don't need the ,.
Sep 3 '15 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 '15 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 '14 at 22:17
• Also, 1000000 can be written 1E6
– mob
May 7 '15 at 21:02
• Updated my answer. Thanks @mob Oct 3 '15 at 17:42
• 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 '15 at 18:10

Julia, 11

primes(10^6)

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

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 '14 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 '12 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 '16 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 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 '16 at 0:15
• Both are. The slow version is just an awful implementation. May 27 '16 at 0:17

NARS2000 APL, 7 characters

⍸0π⍳1e6
• Welcome to Programming Puzzles & Code Golf! Sep 26 '15 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 '12 at 23:05 • @PeterTaylor Thanks, using multiplication there is a very neat trick. May 27 '12 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 '14 at 15:10 • @PeterTaylor good one, thanks! I've edited my code. Apr 1 '14 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 '14 at 13:21 • @PeterTaylor oh, yes it is Jul 14 '14 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. 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 '13 at 18:32 • @SvenHohenstein Thanks, corrected. Nov 20 '13 at 7:51 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 '14 at 6:59

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
May 13 '14 at 18:40
• @professorfish I assume I should add an explanation? May 13 '14 at 18:41
• yessssssss (putting in extra sssss because of char limit_)
– user16402
May 13 '14 at 18:42
• You need for the proper output (and btw, ¯2π⍳78498 is much simpler).