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

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 :) – chyanog Nov 5 '14 at 13:38
• Would be nine bytes in mthmca, if that were to be released. – Michael Stern 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. – celtschk Jun 25 '17 at 9:43
• @celtschk I don't know if I missed or disregarded that five years ago. – Mr.Wizard Jun 25 '17 at 19:11
• Well, I definitely missed that it was from five years ago :-) – celtschk Jun 25 '17 at 19:36

Python 3, 46 bytes

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

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.

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 – manav m-n Jul 21 '14 at 7:32
• @Manav, perhaps you compiled without optimizations. It relies on a good optimizer, which will remove the recursion. – ugoren Jul 21 '14 at 10:50
• Yes adding -O3 to gcc solved the problem!! – manav m-n Jul 21 '14 at 11:23
• This method is insane. I love it. – Todd Lehman 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);} – Albert Renshaw 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. – orion May 14 '14 at 18:53
• @orion That would make it 11 characters – Axoren Oct 31 '14 at 7:18
• @Axoren that does not include the ' at the end – Stan Strum 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' – Delan Azabani May 26 '12 at 9:13
• yes you're right. I wrote my sed command clean, not golfed :P – saeedn May 26 '12 at 9:15
$p 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.

• awk '$0=$2*!$3' is awksome cool! – yeti May 15 '14 at 0:36 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) – Ventero 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. – Cristian Lupascu May 26 '12 at 19:53 • Shorter version require'prime';p Prime.take 78498. – Hauleth Nov 25 '13 at 10:46 • @ŁukaszNiemier Great! I think that's so different that you can post it as a separate answer. – Cristian Lupascu Nov 25 '13 at 14:08 • Good use of some good ol' country boy mathn' – DoctorHeckle Apr 27 '16 at 20:22 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! – Digital Trauma May 13 '14 at 21:23
• Shave off one character: seq 1e6|factor|grep -oP "(?<=: )\d+$" with a perl-grep lookbehind – Digital Trauma 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. – Digital Trauma May 14 '14 at 16:21
• @DigitalTrauma added – 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. – dan04 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. ;) – Dogbert Oct 31 '13 at 10:58
• why are there extra spaces after print and in (> 0)? – proud haskeller Aug 4 '14 at 2:52
• nice catch! thanks – pt2121 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. – user2845840 Jul 29 '15 at 22:21
• @user2845840 ok thanks. good idea! – pt2121 Jul 30 '15 at 0:47

APL, 15

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

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

• How? Can you give a deskription? – Rasmus Damgaard Nielsen Aug 31 '15 at 20:39
• You need a in front to make one number per line, and you don't need the ,. – Adám 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.) – Adám 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 – Gowtham 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.) – Codefun64 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[\ . – Gareth 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.

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

NARS2000 APL, 7 characters

⍸0π⍳1e6
• Welcome to Programming Puzzles & Code Golf! – Dennis 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$\%!}?=}, – Peter Taylor May 26 '12 at 23:05 • @PeterTaylor Thanks, using multiplication there is a very neat trick. – Cristian Lupascu 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 *. – Peter Taylor Apr 1 '14 at 15:10 • @PeterTaylor good one, thanks! I've edited my code. – Cristian Lupascu 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? – Peter Taylor Jul 14 '14 at 13:21 • @PeterTaylor oh, yes it is – aditsu 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. 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) – Ali1S232 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. – Erik the Outgolfer Jul 17 '16 at 21:57 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. – Sven Hohenstein Nov 17 '13 at 18:32 • @SvenHohenstein Thanks, corrected. – plannapus 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. – orion May 15 '14 at 6:59

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. – Jeppe Stig Nielsen May 29 at 22:39