56
\$\begingroup\$

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.

\$\endgroup\$
  • 12
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor May 26 '12 at 8:42
  • \$\begingroup\$ Ah, yes, I was worried about this question being too similar to the plethora of prime number-related questions already around. \$\endgroup\$ – Delan Azabani May 26 '12 at 8:44
  • 2
    \$\begingroup\$ @GlennRanders-Pehrson Because 10^6 is even shorter ;) \$\endgroup\$ – ɐɔıʇǝɥʇuʎs May 14 '14 at 5:20
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – Computronium Jun 25 '17 at 21:45
  • 1
    \$\begingroup\$ @ɐɔıʇǝɥʇuʎs How about 1e6 :-D \$\endgroup\$ – Titus Mar 3 '18 at 2:09

103 Answers 103

3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ This is sinister black magic. \$\endgroup\$ – user16402 May 13 '14 at 18:40
  • \$\begingroup\$ @professorfish I assume I should add an explanation? \$\endgroup\$ – Oberon May 13 '14 at 18:41
  • \$\begingroup\$ yessssssss (putting in extra sssss because of char limit_) \$\endgroup\$ – user16402 May 13 '14 at 18:42
  • \$\begingroup\$ You need for the proper output (and btw, ¯2π⍳78498 is much simpler). \$\endgroup\$ – Adám Jun 28 '16 at 20:05
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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")
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ quite a big variety of speeds here, one of my answers took 4.5 seconds \$\endgroup\$ – user16402 May 14 '14 at 16:38
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Giving last prime number can save one character. \$\endgroup\$ – Prince John Wesley May 27 '12 at 13:28
2
\$\begingroup\$

Octave, 12, 11

primes(1e6)

Write 1000000 as 1e6

\$\endgroup\$
  • 1
    \$\begingroup\$ 1e6 is even shorter ;) \$\endgroup\$ – jpjacobs Oct 30 '13 at 13:31
  • \$\begingroup\$ Editted in. Thanks for the info :) \$\endgroup\$ – MrD Oct 30 '13 at 21:17
2
\$\begingroup\$

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++;);
\$\endgroup\$
2
\$\begingroup\$

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#^        #<^#<@
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I think that should be INT(I/J) not I/I. Btw. that´s 56 bytes; and 56 characters (the last line needs a RETURN as well so it gets recognized). 1F┌I=2TO10^6:F┌J=2TOI/2:IF(I/J!=INT(I/I))N─:?I and 2N─I is four characters shorter and six bytes smaller. Nice approach though. \$\endgroup\$ – Titus Mar 3 '18 at 12:31
  • \$\begingroup\$ Oh and for those that think that integer varibales would be faster: They´re not. Commodore Basic transforms integer values to float for calculations. \$\endgroup\$ – Titus Mar 3 '18 at 12:38
2
\$\begingroup\$

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]));
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save a byte by incrementing in the compare for(i=1,l=[];++i<1e6;) \$\endgroup\$ – andrewarchi Jun 14 '17 at 17:01
2
\$\begingroup\$

MATL, 5 bytes

1e6Zq

Explanation:

1e6   % push 10000 to stack
   Zq % primes up to top-of-stack number
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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)

\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Martin Ender Jun 25 '17 at 21:16
  • \$\begingroup\$ I improved the formatting and added in a Try It Online link. Also 5 bytes \$\endgroup\$ – caird coinheringaahing Dec 9 '17 at 12:34
  • \$\begingroup\$ @cairdcoinheringaahing not sure if it was in the syntax at the time, but you could replace 10*6 with ȷ6 to save a byte. \$\endgroup\$ – Nick Kennedy Jun 15 at 8:21
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You can save a byte changing ε, to » (join by newlines; after which the result is implicitly output). \$\endgroup\$ – Kevin Cruijssen Nov 9 '18 at 14:47
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Haskell, 65 chars

main=print[x|x<-[2..999999::Int],null[i|i<-[2..x-1],mod x i==0]]
\$\endgroup\$
  • \$\begingroup\$ Nice. Could you save a few by removing the ::Int ? \$\endgroup\$ – brander Mar 2 '17 at 4:08
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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))))))))
\$\endgroup\$
1
\$\begingroup\$

Matlab (12)

Pretty simple=)

primes(1e6)'
\$\endgroup\$
  • \$\begingroup\$ So simple that there is already codegolf.stackexchange.com/a/6274/21348 \$\endgroup\$ – edc65 Aug 3 '14 at 16:48
  • \$\begingroup\$ Oh, didn't see that one, but I have to say that mine is way shorter=) \$\endgroup\$ – flawr Aug 3 '14 at 17:19
1
\$\begingroup\$

Java, 183 characters

import java.util.stream.*;
class P{public static void main(String[]a){
IntStream.range(1,1000000).filter(i->!IntStream.range(2,i).anyMatch(j->i%j==0)).forEach(System.out::println);
}}

Performance is not optimal, but code is well readable. For faster computation could be code extended to use parallel streams:

import java.util.stream.*;
class P{public static void main(String[]a){
IntStream.range(1,1000000).parallel().filter(i->!IntStream.range(2,i).anyMatch(j->i%j==0)).forEachOrdered(System.out::println);
}}
\$\endgroup\$
  • \$\begingroup\$ I think you can remove some of the newlines. \$\endgroup\$ – SuperStormer Jun 26 '17 at 22:52
1
\$\begingroup\$

Java - 101 characters

Ungolfed version:

for(int i=3, j; i < 1000000; i++) {
    for(j = 2; j < i / 2; j++)
        if (i % j ==0)
            break;
    System.out.printf(i % j != 0 ? i + "%n" : "");
}

Golfed version:

for(int i=3,j;i<1000000;i++){for(j=2;j<i/2;j++)if(i%j==0)break;System.out.printf(i%j!=0?i+"%n":"");}
\$\endgroup\$
  • \$\begingroup\$ @Martin Büttner Oups. Fixed it. \$\endgroup\$ – Barracuda Aug 4 '14 at 21:20
  • \$\begingroup\$ IDK, if that is an accepted format in Codegolf, you have to wrap it into a function, a lambda or a program. It helps other people to test your code faster and gives everyone using the same language a fair playing ground. \$\endgroup\$ – HopefullyHelpful May 26 '16 at 14:13
1
\$\begingroup\$

Perl6 - 47

for 1..10**6 {(1 x$_)~~/^(11+?)$0+$/ or say $_}

credit to Gowtham's perl solution

  • 1000000 better written as 10**6
  • print "$_\n" became say $_
  • =~ became ~~
  • needed to add whitespace in front of the x operator
\$\endgroup\$
  • \$\begingroup\$ you can use superscript version of 106 > 10⁶ so you can shorten range from 1..106 to ^10⁶ + you can move the for on the right side and it becomes 41 chars (1 x$_)~~/^(11+?)$0+$/ or say $_ for ^10⁶ \$\endgroup\$ – Demayl Jun 15 '17 at 7:00
  • \$\begingroup\$ You could also use .say instead of say $_. \$\endgroup\$ – bb94 Apr 19 at 3:56
1
\$\begingroup\$

Dart - 75 chars

Loop based version:

main(i,j){for(i=2;i<1e6;i++)l:{for(j=2;j<i;j++)if(i%j<1)break l;print(i);}}

It's much faster if you change j<i to j*j<=i, but not shorter!

Alternative List based version (107 chars) Not going to win any records without a shorter way to generate the list.

main(p,q){p=new List.generate(999998,(x)=>x+2);while(!p.isEmpty){print(q=p[0]);p.removeWhere((x)=>x%q<1);}}

Ungolfed

    main(p,q) { 
      p = new List.generate(999998, (x) => x + 2);
      while (!p.isEmpty) { 
        print(q = p[0]);
        p.removeWhere((x) => x%q < 1);
      }
    }
\$\endgroup\$
1
\$\begingroup\$

Bacchus, 34 bytes

\n[2..1E6]a(Öp:a(·=1.Öw)?),·¨

Explanation:

\n            Prepare the output to be one in each line

[2..1E6]      Generates an array from 2 to 1000000

:a            Push the array to the stack

(),·¨         For each element on the array we previously pushed to the stack

Öp:a          If current element of the for-each loop is Prime push 1 to the stack. Otherwise, push 0.

(·=1.Öw)?     If last pushed element is 1 then print current element of the for each loop.

Most of the code is used to output each prime in different lines. Otherwise a much shorter code (10 bytes) would be

[2..1E6]p#
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.