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

1
\$\begingroup\$

LiveScript - 71 bytes

I was goofing around, trying to golf Sieve of Eratosthenes. I'm quite happy with the result. It uses prelude.ls.

x=1e6;[2 to x]|>unfoldr ([x]:l)->|l>[]=>[console.log<|x,l|>filter (%x)]

It outputs to the console. You can try the code in http://livescript.net - I recommend using lower limit than 1e6, because it gets slow at those numbers and probably hangs your browser for a while. I couldn't find a way to stop LS from inlining [2 to 1e6], so I had to creae a var for it.

Just for the sake of it, the original function I mangled the first one from:

p=->[2 to it]|>unfoldr ([x]:l)->|l>[]=>[x,l|>filter (%x)]
\$\endgroup\$
1
\$\begingroup\$

JS, 100 67 57

By xem and subzey

Execute this in the browser's console or nodeJS.

Short version: 57b. (it's very long to end: ~ 20 min)

for(i=1;1e6>++i;p&&console.log(i))for(p=j=i;j-->2;)p*=i%j

Faster version, 100b (ends in ~ 1 min)

p=[];for(i=2;1E6>i;i++)for(t=0,j=i;1E6>j;j+=i)t&&(p[j]=1),t=1;for(i=2;1E6>i;i++)p[i]||console.log(i)
\$\endgroup\$
1
\$\begingroup\$

Prolog - 129

Not a very short variant, but reasonably fast. A simple implementation of the Sieve of Eratosthenes.

:-initialization m.
F+S+X:-G is F,(G=<1e6,X=G;G<1e6,(G+S)+S+X).
m:-assert(i-1),2+1+I,\+i-I,write(I),nl,I*I+I+J,assert(i-J),1=0;!.

Invocation:

time swipl -qf ./prime.pl < /dev/null | wc -l

78498

real    0m3.646s
user    0m3.468s
sys     0m0.264s

Readable:

:- initialization(main).

between2(From, _, X) :-
    X is From,
    X =< 1000000.
between2(From, StepSize, X) :-
    Y is From,
    Y < 1000000,
    between2(Y + StepSize, StepSize, X).

main :-
    assert(stroke(1)), % shorter than ":-dynamic stroke/1."
    between2(2, 1, I),
    \+ stroke(I),
    write(I), nl,
    between2(I*I, I, J),
    assert(stroke(J)),
    fail.
main.
\$\endgroup\$
1
\$\begingroup\$

Perl, 75

map{my($a,$b)=($_,0);for(2..$a-1){$a%$_==0&&$b++}$b||print"$a\n"}(2..10**6)
\$\endgroup\$
1
\$\begingroup\$

Jagl Alpha 1.2 - 14 bytes

Not competing, language is younger than question

1e6r{m}%{PZp}/

Prints on separate lines.

\$\endgroup\$
  • \$\begingroup\$ Is this language younger than the question? \$\endgroup\$ – trichoplax Dec 30 '14 at 0:27
  • \$\begingroup\$ Yes, I am not competing. Clarified in the answer @githubphagocyte \$\endgroup\$ – globby Dec 30 '14 at 0:27
  • \$\begingroup\$ @githubphagocyte :) \$\endgroup\$ – globby Dec 30 '14 at 0:33
1
\$\begingroup\$

Pyth - 14 12 chars

Fkr2^T6IqlPk1k

Thanks so much to @FryAmTheEggman for removing two chars from filter and ![1:] instead of ==1. As you probably can guess I learned Pyth literally yesterday. :)

jbf!tPTtU^T6

Omg I actually beat Mathematica builtins. Its very simple it just loops through 2 to a million and uses trick that prime numbers have one number in thier prime factorization which pyth happens to have a function for.

jb:    Join with \n as sperator
f:     filter by
!tPT:  not tail of prime factorization of loop variable(tail would be falsey if len 1 so then negate)
tU^T6:  filter through range 2-million

It does take a verrrrrry long time to run, but if you want to just see it run, you can change the 6 to a 2 for primes under hundred.

\$\endgroup\$
  • \$\begingroup\$ Using pyth's filter function is a tad shorter: jbf!tPTtU^T6. This also saves a char by checking len(prime_factors(n)[1:])>0, which could also be added to your code: I!tPk. (This works because an empty list is False, and a list of any other length is True) Good luck with Pyth ;) \$\endgroup\$ – FryAmTheEggman Dec 30 '14 at 5:33
1
\$\begingroup\$

Ruby 37 32

(2..1e6).map{|x|p x if x.prime?}
\$\endgroup\$
  • \$\begingroup\$ yeah that makes so much sense. THanks :) \$\endgroup\$ – shivam Mar 9 '15 at 12:35
  • \$\begingroup\$ Actually, I can't find any documentation of prime?. Have you tested this? \$\endgroup\$ – Martin Ender Mar 9 '15 at 12:38
  • \$\begingroup\$ yeah it works great. Here: ruby-doc.org/stdlib-1.9.3/libdoc/prime/rdoc/… \$\endgroup\$ – shivam Mar 9 '15 at 12:40
  • \$\begingroup\$ This only works if the Prime module is loaded. You need to require 'prime' otherwise you get NoMethodError: undefined method `prime?' for 2:Fixnum \$\endgroup\$ – daniero Sep 3 '15 at 17:38
1
\$\begingroup\$

T-SQL, 141

Assuming a resultset is valid output, here's code that works with SQL Server 2008 R2. It uses a table to store previously found primes. The table is initialized with 2, and all odd integers greater than that are checked against the contents of the table at the point in time of the check. Runtime and efficiency obviously were not concerns....

DECLARE @ INT=3SELECT 2 p INTO # l:IF NULL=ALL(SELECT 1FROM # WHERE @%p=0)INSERT # VALUES(@)SET @+=2IF @<1e6GOTO l SELECT p FROM # ORDER BY p
\$\endgroup\$
1
\$\begingroup\$

Sage, 28 bytes

for i in primes(1e6):print i

Try it online

\$\endgroup\$
  • \$\begingroup\$ @FryAmTheEggman It's Python 2 \$\endgroup\$ – Mego Apr 27 '16 at 19:05
1
\$\begingroup\$

Pyth, 9 bytes

V^T6IP_NN

Explanation:

V starts a for loop from 0 to the next number, keeping N as the value
T = 10 and so ^T6 = 10^6 = 1000000
I is if, P_N checks if N is prime and returns True or False based on the result.
The final N is just to print it.

I'm new to Pyth so it's likely not the best solution. Any suggestions are welcome!

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

PHP, 100 95 bytes

It works by iterating 1,000,000 times and then using this regular expression on a unary number to check if it's prime. It's not the smallest PHP solution submitted, but thought I'd submit it just so it's here.

for($i=0;$i<=1e6;$i++)if(preg_match('/^1?$|^(11+?)\1+$/',str_repeat("1",$i))==0)echo$i.PHP_EOL;

Matchu explains how the regular expression works - https://stackoverflow.com/a/3296068/3000179

First 50: https://eval.in/746404

\$\endgroup\$
  • \$\begingroup\$ Can you remove the space between for($i=0;$i<=1e6;$i++) and everything else? \$\endgroup\$ – CalculatorFeline Mar 2 '17 at 15:15
  • \$\begingroup\$ @CalculatorFeline yep, thanks! \$\endgroup\$ – ʰᵈˑ Mar 2 '17 at 15:47
  • \$\begingroup\$ Great algorithm! 28 bytes shorter: while(++$i<1e6)preg_match('/^1?$|^(11+?)\1+$/',$s.=1)||print"$i\n"; (not tested). Save one more byte with a literal newline. Have you tried ereg instead of preg_match? That would save another 8 bytes, shrinking your solution to 58 bytes. \$\endgroup\$ – Titus Mar 3 '18 at 2:18
1
\$\begingroup\$

Ohm, 3 bytes (CP437)

Non-competitive, obviously, but I don't think anyone will mind since this question is almost 5 years old ;)

6°P
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 7 bytes

Since there is not yet an answer in 05AB1E.

T6mGNp–

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Why is the input for this 22? \$\endgroup\$ – Magic Octopus Urn Jun 14 '17 at 16:56
  • \$\begingroup\$ @carusocomputing There is no reason for that... removed it \$\endgroup\$ – kalsowerus Jun 15 '17 at 5:49
1
\$\begingroup\$

Java 8, 100 97 92 bytes

o->{for(int i=1,n,j;i++<1e6;){for(n=i,j=2;j<n;n=n%j++<1?0:n);if(n>1)System.out.print(n);}}

-3 bytes by thanks to @Nevay.
-5 bytes by converting Java 7 to Java 8.

I know there are already a few other Java answers. I didn't knew which to choose to put the comment on with my golfed method, so I decided to post this separate answer. Not to mention it's slightly or a lot shorter than any of the other current Java answers so far.

Explanation:

Try it here.

o->{                          // Method with empty unused parameter and no return-type
  for(int i=1,n,j;            //  Initialize some integers
      i++<1e6;){              //  Loop (1) from 2 through 1,000,000 (exclusive)
    for(n=i,j=2;              //   Set some integers
        j<n;                  //   Inner loop (2) from 2 through `n` (exclusive)
      n=                      //    Change `n` to:
        n%j++<1?              //     If `n` is divisible by `j`:
         0                    //      Change `n` to 0 (which means it isn't a prime)
        :                     //     Else:
         n                    //      Leave `n` unchanged
    );                        //   End of inner loop (2)
    if(n>1)                   //   If `n` is larger than 1, which means it's a prime:
      System.out.println(n);  //    Print `n` + new-line
  }                           //  End of loop (1)
}                             // End of method
\$\endgroup\$
  • 2
    \$\begingroup\$ You can use if(n>1)System.out.println(n); instead of System.out.print(n>1?n+"\n":""); to save 3 bytes. \$\endgroup\$ – Nevay Aug 11 '17 at 12:39
1
\$\begingroup\$

Pyth, 12 bytes

V^T6IqlPN1N

Explanation

V^T6 - For loop using looping variable N in range 0 to 10 ^ 6

IqlPN1 - If len(prime_factors(n)) == 1

N - implicity print n (if it is prime)

Try running the code here: https://pyth.herokuapp.com/?code=V%5ET6IqlPN1N&debug=0

Note that this seems to take too long to run on the online interpreter, so try replacing V^T6 with V^T3, which will run (and clearly if it can print primes up to 1,000, it will work with 1,000,000)

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Martin Ender Aug 12 '17 at 9:59
1
\$\begingroup\$

Pyt, 9 bytes

78497ǰƖřᵽ

Try it online!

78498ǰƖřᵽ
78497      - push 7, 8, 4, 9, and 7 on the stack
    ǰ      - join everything on stack w/no delimiters
     Ɩ     - casts to int
      ř    - construct range from 78498 to 1 ([1,2,3,..., 78497, 78498])
       ᵽ   - push xth prime for every item in list

Doesn't meet the timeout rq on tio, but it would work, you can try it with lower numbers the reason for 78498 is that that is the 0 indexed prime under a million

\$\endgroup\$
  • \$\begingroup\$ You can save a byte (or two) and get it to not time out on tio: 6ᴇřĐṗ*žÁ. The Á is only to make the output match the format specified in the question, and can be removed if the output can be an array. \$\endgroup\$ – mudkip201 Mar 4 '18 at 14:28
  • \$\begingroup\$ I feel like that's different enough to post as your own answer, but if you don't want to, I'll update. \$\endgroup\$ – FantaC Mar 4 '18 at 20:56
  • \$\begingroup\$ I'll post it as a separate answer \$\endgroup\$ – mudkip201 Mar 4 '18 at 20:59
1
\$\begingroup\$

C (gcc) 65 bytes

j;f(i){for(;++i<1e6;)for(j=2;!printf("%d\n"+(i>j)*3,i)&&i%j++;);}

Try it online! ( stops at 1000 )

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

Tcl, 104 bytes

set i 2
time {set p 1;set j 2;while \$j<$i {if $i%$j==0 {set p 0};incr j};if $p {puts $i};incr i} 999998

Try it online!

Unfortunately I could not find an online Tcl interpreter which does not time out running it.


Tcl, 110 bytes

set i 2
time {set p 1;set j 2;while \$j<$i {if $i%$j==0 {set p 0;break};incr j};if $p {puts $i};incr i} 999998

Try it online!

tcl, 115

set i 2
time {set p 1;set j 2;while \$j<$i {if ![expr $i%$j] {set p 0;break};incr j};if $p {puts $i};incr i} 999998

demo


tcl, 201

My still not golfed answer:

for {set i 2} {$i<$1000000} {incr i} {
    set p 1
    for {set j 2} {$j<$i} {incr j} {
        if {[expr $i%$j] == 0} {
            set p 0
            break
        }
    }

    if $p {puts $i}
}

demo

\$\endgroup\$
  • \$\begingroup\$ 102 \$\endgroup\$ – ASCII-only Apr 1 at 5:32
  • \$\begingroup\$ 100 \$\endgroup\$ – ASCII-only Apr 1 at 5:52
  • \$\begingroup\$ 94 - note my previous bytecounts should be 2 longer since i lowered loop limit \$\endgroup\$ – ASCII-only Apr 1 at 5:57
  • \$\begingroup\$ 88 \$\endgroup\$ – ASCII-only Apr 1 at 6:01
0
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ i=1;while(++i<E) can be improved to for(i=1;++i<E;). for(j=2*i;j<x;j+=i)s[j]=1; can be improved to for(j=1;++j<x;)s[j*i]=1; \$\endgroup\$ – Peter Taylor May 26 '12 at 8:48
  • \$\begingroup\$ Thanks. For your second improvement, though, considering that j would no longer be a direct index to the sieve, wouldn't comparing against x cause the program to significantly overrun the array? \$\endgroup\$ – Delan Azabani May 26 '12 at 8:54
  • \$\begingroup\$ Fair point. One big improvement still possible, though: use a single loop. Can't think how I missed it earlier. \$\endgroup\$ – Peter Taylor May 26 '12 at 9:40
  • \$\begingroup\$ As in, using one loop in total, or replacing the first pair of loops with one loop, resulting in two loops? I don't think the former is possible, as it'd mean printing while the sieve is in an incomplete state. \$\endgroup\$ – Delan Azabani May 26 '12 at 9:42
  • \$\begingroup\$ Sure it's possible. The part of the sieve up to i is complete. \$\endgroup\$ – Peter Taylor May 26 '12 at 10:59
0
\$\begingroup\$

Python, 68

print[a for a in range(2,999999)if all(a%b for b in range(2,a/2+1))]

Sadly, there's no hope in seeing it terminate within any reasonable time frame...

\$\endgroup\$
0
\$\begingroup\$

Haskell, 126 chars, Using Sieve of Eratosthenes

import Data.Set 
g i n m|i>n=[]|member i m=g(i+1)n m|1<2=i:g(i+1)n(fromList[i*i,i*i+i..n]`union`m)
main=print$g 2(10**6)empty

Run quite fast on my machine.

% ghc primeList1.hs -O
[1 of 1] Compiling Main             ( primeList1.hs, primeList1.o )
Linking primeList1 ...

% time ./primeList1 >/dev/null
./primeList1 > /dev/null  5.04s user 0.05s system 99% cpu 5.100 total
\$\endgroup\$
0
\$\begingroup\$

Ruby, 94 (optimized for speed, 2.655 secs)

(a=[*2..n=1e6]).each{|p|next if !p
break if p*p>n
(p*p).step(n,p){|m|a[m]=nil}}
puts a.compact

Ran in 2.655 seconds on my machine, which is pretty good considering how slow Ruby is.

Here's how I timed it:

t = Time.now

(a=[*2..n=1e6]).each{|p|next if !p
break if p*p>n
(p*p).step(n,p){|m|a[m]=nil}}
puts a.compact

puts Time.now - t

It takes a ridiculously long time to output to stdout, so I did sieve.rb > sieve.txt (on Windows).

\$\endgroup\$
0
\$\begingroup\$

Groovy - 65 chars

This feels like cheating, but... Output confirmed against other solutions (i.e. 'probable prime' is accurate for such small values)

n=new BigInteger(1);78498.times{println n=n.nextProbablePrime()}

The code uses the fact that there are 78498 primes that fit the requirement.

\$\endgroup\$
0
\$\begingroup\$

C# & LinqPad 71

As usual directly executable in LinqPad

for(int i=0;++i<1e6;){for(int b=1;++b<i;)if(i%b==0)goto a;i.Dump();a:;}

Takes about 7 minutes on my computer.

\$\endgroup\$
0
\$\begingroup\$

><> (Fish), 54 51 bytes

11+:aa*:\/&~!
:**=?;2&\
:v?=&:&:<^!?%&+1:&
.\:nao90

There's Befunge but no ><>, so I thought "might as well". Uses the ever so slow trial division.

\$\endgroup\$
0
\$\begingroup\$

Golfscript, 55

{.2<{}{:l;1{).l\%}do}if}:r;10 6?,{..r={" "+print}{}if}%

Old code:

{:q-2:r\,{1+}%{q\%0={1r+:r}{}if}%;;r}:f 1000000,{f!},\;(;n*

WARNING. This program uses an extremely slow algorithm, it takes ~15 seconds for it to display the 1000 first primes and the time grows exponentially. If you want to use it, change the 1000000 in the code to something lower.

\$\endgroup\$
0
\$\begingroup\$

Smalltalk - 22 characters

Integer primesUpTo:1e6

The dialect is Smalltalk/X; other dialects have the same or a similar method in Integer.

Exec. time (measured with: "Time millisecondsToRun:[...]" is 90ms on my somewhat older (2010) 2.6Ghz Mac.

Evaluating "(Integer primesUpTo:1e6) size" returns: 78498

\$\endgroup\$
0
\$\begingroup\$

Perl, 35

use ntheory":all";print_primes(1e6)

Fast and small vs. the usual golf horrifically slow regex. I used this earlier for 39 characters:

use ntheory":all";say for@{primes(1e6)}
\$\endgroup\$
0
\$\begingroup\$

Ruby, 118 117 bytes

n=999984;t=true;a=[t]*n;(2..Math.sqrt(n).round).each{|i|a[i]&&(i..n/i).each{|j|a[j*i]=!t}};(2..n).each{|i|a[i]&&p(i)}

Run Time:

0.53s user 0.13s system 92% cpu 0.714 total
\$\endgroup\$
0
\$\begingroup\$

Swift 2, 79 bytes

Utilises the Sieve of Eratosthenes.

var r=[Int](2..<Int(1e6));while r.count>0{print(r[0]);r=r.filter{$0%r[0] != 0}}

Notes:

  • Solution without the sieve needs two extra bytes.
  • Takes ~14 mins on i5 3.5 GHz; or ~40 secs if compiled with optimisations.
  • Use -O flag with swiftc to turn on optimisations.
\$\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.