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

NARS2000 APL - 9 characters

¯2π⍳2π1e6

Quite a boring answer.

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

Answer 2

Commodore 64 Basic, 55 characters

1F┌I=2TO10^6:F┌J=2TOI/2:IF(I/J=INT(I/I))G┌3
2N─:?I
3N─I

PETSCII substitutions: ┌ = SHIFT+O, ─ = SHIFT+E

Incredibly slow: first, because the algorithm is extremely inefficient (it tries dividing by every value less than half the candidate number), second, because the Commodore 64 is slow, and third, because Commodore Basic does all its math in emulated floating-point on an 8-bit CPU.

Theoretical solution, 82 characters

1M=10^6:D╮S(M):F┌I=2TO1000:F┌J=I^2TOMST─I:S(J)=-1:N─:N─:F┌I=2TOM:IF(N┌S(I))T|:?I
2N─

╮ = SHIFT+I, ┌ = SHIFT+O, ─ = SHIFT+E, | = SHIFT+H

If this program could run on an actual Commodore 64, it would be much faster than the above. However, it can't: the sieve alone would take 5,000,007 bytes out of the 38,911 bytes a C64 has available for Basic programs. Note the use of -1 instead of 1 when denoting composite values in the array: C64 Basic doesn't have a true boolean negation; NOT performs a two's complement instead.

Answer 3

HPPPL, 90 89 chars

(HP Prime Programming Language), for the HP Prime color graphing calculator.

export p()begin local i;for i from 2 to 1e6 do if isprime(i)=1 then print(i) end;end;end;

Output to the terminal is quite slow on the Prime, so the program takes quite a while to run. Printing out all primes using the emulator takes about 88 seconds on my i5 2410M laptop.

As my google account is messed up, I have to start all over again with a new account... so be it. My photo and name are the same as before ;)

You can try out the program with the free HP Prime emulator available here:

http://www.hp-prime.de/en/category/13-emulator

Answer 4

Vim, 34 bytes

6@=9<CR>o<Tab>0<Esc>V{g<C-A>dj=:g/\v^(<Tab><Tab>+)\1+</d<CR>

This is a direct adaptation of my top solution to Prime Numbers. The difference is... here I have to go up to a million. This forces a cool tactic to put 999999 into the readahead, but it also makes this solution impossible to run. You won't even get past the setup making the number array, because you'd need to fill more than half a terabyte of RAM (without overhead). And if you ever got to the regex algorithm... well, it sucks. You'd never finish.

This solution requires :set autoindent noexpandtab, which you might have set already, might not. It also requires computer hardware that doesn't exist.

• 6@=9<CR>: Cool trick to write 999999 in 5 bytes. Integer 9 gets evaluated into the expression register as text. That "macro" is run 6 times.
• o<Tab>0<Esc>: Make N (999,999) lines of zeroes, with stair-step indent. This is kind of like what happens when you paste in insert mode without doing :set paste.
• V{g<C-A>: Visual increment to turn the 0s into a list of numbers 1-999,999. Conveniently leaves cursor on top.
• dj: Remove the blank (zero) and 1 lines.
• =:: Vim users rarely think of the : command as an operator, but it is one (a charwise operator, surprisingly). Runs the = out to where the : command would move the cursor (top to bottom in this case).
• \v^(<Tab><Tab>+)\1+<: Regex that matches a composite number of tabs. If you haven't, watch the VimCast episode, which covers an old version of this solution. The :g//d will delete those lines. The cursor will end on the last remaining line, which will act as the operator for = to remove all indent.

Vim, 36 bytes (actually runs)

• 6@=9<CR>O0<Esc>V{g<C-A>:%norm~V$EkdYo@0D@.<C-O>@.<CR>d

This :normal macro is a proper sieve of Eratosthenes that cleans up after itself. I actually ran this out to 1,000,000. Took 10-15 minutes. The algorithm is quite good, but the data structure (array of lines in Vim) comes with a big toll. I wrote about it in more detail a long time ago.

Answer 5

APL (Dyalog), 15 chars

⍪(⊢~∘.×⍨)1↓⍳1E6

Try it online! (only goes until one thousand as TIO does not allot enough memory for a million)

⍳1E6 first million ɩntegers

1↓ drop one

(…) apply the following tacit function:

 ⊢ the argument (all the numbers 2…1000000)

 ~ except those that are in

 ∘.×⍨ the multiplication table (using the argument as both vertical and horizontal axis)

⍪ table (makes list into column)

Answer 6

PHP, 55 53 51 bytes

for($n=1;1e6>$i=$n++;$i||print"$n
")while($n%$i--);

Run with -nr or try it online. (TiO only runs to 10K; 1M would exceed the time limit.)

The outer loop runs $n from 1 to 1 million.
The inner loop is the primality test: loops $i down from $n-1 until $i is a divisor of $n.
If that divisor is 1, $n is a prime and will be printed in the post-condition of the outer loop.

Answer 7

QBASIC, 75 bytes

FOR I=2 TO 1e6
    FOR J=2 TO I^.5
        IF I MOD J=0 THEN:GOTO X
    NEXT
    ?I
X:NEXT

I could have saved a character by going with FOR J = 2 TO I/2 but the run time was seriously slow. Runs at a much saner speed by only going to Sqrt I.

Answer 8

F#, 100 94 bytes

let p n=
    let rec c i=i>n/2||(n%i<>0&&c(i+1))
    c 2
for n in 1..1000000 do if p n then printfn "%i" n

let p n={2..n-1}|>Seq.forall(fun x->n%x<>0)
{2..1000000}|>Seq.filter p|>Seq.iter(printfn "%i")

Answer 9

FORTRAN 90, 80 bytes

DO I=2,1E2;D=1;DO J=2,I**.5;IF(MOD(I,J)==0)D=0;ENDDO;IF(D==1)PRINT*,I;ENDDO;END

This is the same as below, but in a newer and less rigorous version.

---

FORTRAN 77, 104 95 bytes

      DOI=2,1E6;D=1;DOJ=2,I**.5;IF(MOD(I,J).EQ.0)D=0;
      ENDDO;IF(D.EQ.1)PRINT*,I;ENDDO;END

Works with gfortran. Not sure if the DO I=... and DO J=... works without spaces in other compilers.

(Modification: program name supressed; I just learned that it's optional!)

Answer 10

Python, 75

print filter(lambda n:n==2 or all(n%i for i in range(2,n)),range(15485864))

Not terribly efficient though, it actually gives me a out of memory error in Jython.

Here's a (slightly) more efficient version:

import math
print [2]+filter(lambda n:all(n%i for i in xrange(3,int(math.sqrt(n))+1,2)),xrange(3,15485864,2))

This version took approximately 8 minutes to run.

Answer 11

Scala, 58

2 to 1000000 map{x=>if(2 to x/2 forall(x%_!=0))println(x)}

or

2 to 1000000 filter{x=>2 to x/2 forall(x%_!=0)}map println

Answer 12

Haskell, 65 chars

main=print[x|x<-[2..999999::Int],null[i|i<-[2..x-1],mod x i==0]]

Answer 13

Octave, 12, 11

primes(1e6)

Write 1000000 as 1e6

Answer 14

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

Answer 15

PHP - 72 bytes

<?for($i=1;$i++^999999;print$d?~ı.$i:'')for($d=$j=2;$j<$i&&$d=$i%$j++;);

Hexdump:

0000000 3c 3f 66 6f 72 28 24 69 3d 31 3b 24 69 2b 2b 5e
0000010 39 39 39 39 39 39 3b 70 72 69 6e 74 24 64 3f 7e
0000020 f5 2e 24 69 3a 27 27 29 66 6f 72 28 24 64 3d 24
0000030 6a 3d 32 3b 24 6a 3c 24 69 26 26 24 64 3d 24 69
0000040 25 24 6a 2b 2b 3b 29 3b                        
0000048

Kinda slow, could be optimised (for 6 bytes) by division-checking until the square root of each number only, like so:

<?for($i=1;$i++^999999;print$d?~ı.$i:'')for($d=$j=2;$j<sqrt($i)&&$d=$i%$j++;);

Answer 16

Befunge-98, 119 characters

Because if it can be done, it can be done in Befunge! Probably not optimal. Works in 98 but not 93 because of the difference in how many bits a cell can store.

2.300p210pv>a,00g:.2+00>p"d"::**v
>00g1-10g`!|Prime Get> ^|p012!`\<
| %g01g00 <>10g1+10pv  v<
>00g:2+00#^        #<^#<@

Answer 17

PARI/GP, 26 bytes

Simple solution:

forprime(p=2,1e6,print(p))

Less-efficient solutions, one per line:

prodeuler(p=2,1e6,print(p));
apply(n->print(n),primes(78498));
apply(n->print(n),primes([2,1e6]));

Answer 18

Javascript es6 66 bytes

I was surprised to not see JS in here so I thought I'd put in a word for her

//takes about 19 minutes to run on my work pc
for(i=2,l=[];i<1e6;++i)l.every(a=>i/a%1)&&l.push(console.log(i)|i)

Answer 19

MATL, 5 bytes

1e6Zq

Explanation:

1e6   % push 10000 to stack
   Zq % primes up to top-of-stack number

Answer 20

Javascript, 74 73 bytes

saved one byte thanks to Martin Ender

()=>{for(i=0;i<1e6;i++)!/^.?$|^(..+)\1+$/.test('1'.repeat(i))&&alert(i);}

Tests all numbers under 1 million against a regex. Regex Explanation

Answer 21

Jelly, 7 bytes

10*6ÆRY

Try it online!

10*6    # One million in scientific notation (10^6 = 1,000,000).
    ÆR  # List of primes less than one million.
      Y # Join the list with newlines.

Answer 22

Python 2; 67 Bytes

n,p=3,[2]
while n<1e5:exec'print n;p+=[n]'*all(n%x for x in p);n+=2

Checks current number against all previous primes, and if not divisible by any of them, prints number and adds to list

The advantage of the while loop compared to other methods is that python will allow direct comparison against a number of the form "1e5", rather than having to use a long form or convert it to an int

Still takes a long time to run

Answer 23

05AB1E, 6 bytes

6°ÅPε,

Try it online!

Explanation:

6°ÅPε,
6°       Push 1000000 to stack (10^6)
  ÅP     List of all primes < 1000000
    ε,   Print each element of the list

Answer 24

Perl 6, 27 bytes

grep(&is-prime,^𖭞)>>.say

Try it online!

Filters all the primes from 0 to a million minus 1 and then prints.

Answer 25

Vyxal, 4 bytes

k4'æ

Try it Online!

k4   # 1m
  '  # 1...^ filtered by
   æ # is prime?

Answer 26

Japt -R, 6 bytes

L³õ fj

Test it

L³õ fj
L          :100
 ³         :Cubed
  õ        :Range [1,L³]
    f      :Filter
     j     :  Prime

Answer 27

Thunno N, \$ 4 \log_{256}(96) \approx \$ 3.29 bytes

Z6gN

Attempt This Online!

Note: this is very slow (it times out on ATO), so here's a version which prints the primes up to 1000: Attempt This Online!

Explanation:

Z6    # Push 10**6 (1000000)
  g   # Filter (range of ^) for:
   N  #  Primes
      # N flag joins by newlines
      # Implicit output 

Answer 28

C (111)

x=1000000,s[1000000],j;main(i){while(++i<x)for(j=2*i;j<x;j+=i)
s[j]=1;for(i=1;++i<x;)if(!s[i])printf("%d\n",i);}

C (112)

x=1000000,s[1000000],j;main(i){while(++i<x)for(j=2*i;j<x;j+=i)
s[j]=1;i=1;while(++i<x)if(!s[i])printf("%d\n",i);}

C (113, over 25% faster)

x=1000,s[1000000],j;main(i){while(++i<x)for(j=i*i;j<x*x;j+=i)
s[j]=1;i=1;while(++i<x*x)if(!s[i])printf("%d\n",i);}

C (ungolfed)

#include <stdio.h>
int sieve[1000000];
int main(void) {
    int i, j;
    for (i = 2; i < 1000; i++)
        for (j = i * i; j < 1000000; j += i)
            sieve[j] = 1;
    for (i = 2; i < 1000000; i++)
        if (!sieve[i])
            printf("%d\n", i);
    return 0;
}

Answer 29

C - 67

$ cat x.c
main(p,t){for(p=1;t=2,++p<1e6;t<p||printf("%d\n",p))while(p%t++);}
$ wc -c x.c 
67 x.c
$ gcc -O3 x.c -o x
x.c: In function ‘main’:
x.c:1: warning: incompatible implicit declaration of built-in function ‘printf’
$ ./x | wc -l
78498

It's sloooooow... don't ask... :-D

I got an even shorter variant (54 bytes) but unluckily it prints the biggest prime first. ;-(

Maybe it fits in a different code golf... someday... ;-)

Answer 30

Clojure - 95 bytes

This is a simple, unoptimised function which prints the primes.

(defn p[](doseq[i(range 2 1e6):when(every? false?(map #(=(mod i %)0)(range 2 i)))](println i)))

Now, I wanted to create something nice too, so here is a function that creates a lazy infinite list of primes.

(defn primes
  ([]
    (concat [2 3] (primes 5)))
  ([n]
    (lazy-seq
      (first
        (for [i     (range)
              :let  [i (+ i n)]
              :when (every? false? (map #(= (mod i %) 0)
                                        (range 2 (Math/sqrt i))))]
          (cons i (primes (+ i 2))))))))