List of primes under a million

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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++);}

Answer 4

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)'

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

Ruby 34

require'prime';p Prime.take 78498

Answer 9

PowerShell, 47 44 bytes

Very slow, but the shortest I could come up with.

$p=2..1e6;$p|?{$n=$_;!($p-lt$_|?{!($n%$_)})}

PowerShell, 123 bytes

This is much faster; far from optimal, but a good compromise between efficiency and brevity.

 $p=2..1e6;$n=0
 while(1){$p=@($p[0..$n]|?{$_})+($p[($n+1)..($p.count-1)]|?{$_%$p[$n]});$n++;if($n-ge($p.count-1)){break}}
 $p

Answer 10

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+$'

Answer 11

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)

Answer 12

Haskell, 51

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

Answer 13

Ruby 50 41

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

Answer 14

Julia, 11

primes(10^6)

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

Answer 15

APL, 15

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

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

Answer 16

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

Answer 17

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

Answer 18

gs2, 5 bytes

Encoded in CP437:

∟)◄lT

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

Answer 19

C, 91 88 85 82 81 80 76 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.

Answer 20

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)

Answer 21

NARS2000 APL, 7 characters

⍸0π⍳1e6

Answer 22

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=},`

Answer 23

CJam - 11

1e6,{mp},N*

1e6, - array of 0 ... 999999
{mp}, - select primes
N* - join with newlines

Answer 24

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.

Answer 25

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.

Answer 26

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.

Answer 27

Mathematica 25

Assuming you don't know the number of primes less than 10^6:

Prime@Range@PrimePi[10^6]

Answer 28

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.

Answer 29

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.

Answer 30

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.