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

Matlab (12)

Pretty simple=)

primes(1e6)'

Answer 2

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

Answer 3

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":"");}

Answer 4

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

Answer 5

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

Answer 6

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#

Answer 7

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

Answer 8

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)

Answer 9

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.

Answer 10

Perl, 75

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

Answer 11

Jagl Alpha 1.2 - 14 bytes

Not competing, language is younger than question

1e6r{m}%{PZp}/

Prints on separate lines.

Answer 12

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.

Answer 13

Ruby 37 32

(2..1e6).map{|x|p x if x.prime?}

Answer 14

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

Answer 15

Sage, 28 bytes

for i in primes(1e6):print i

Try it online

Answer 16

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!

Answer 17

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

Answer 18

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

Answer 19

05AB1E, 7 bytes

Since there is not yet an answer in 05AB1E.

T6mGNp–

Try it online!

Answer 20

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

Answer 21

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)

Answer 22

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

Answer 23

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 )

Answer 24

Pyt, 8 bytes

6ᴇřĐṗ*žÁ

Try it online!

Explanation:

6ᴇ            Push 1000000
ř             Push [1,2,...,999999,1000000]
Đ             Duplicate top of stack
ṗ             Is each element prime (pushes array of booleans)
*             Multiply top two on stack element-wise
ž             Remove all zeros
Á             Push contents of array onto stack
              Implicit print

Answer 25

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

Answer 26

Rockstar, 128 bytes

X's1
while X-999999
let X be+1
let D be X
P's1
while P and D-2
let D be-1
let M be X/D
turn up M
let P be X/D aint M

if P say X

Try it here (Code will need to be pasted in) - Extremely inefficient; knock a few 9s off the second line to have it complete in a sane amount of time.

Answer 27

Factor + math.primes, 22 bytes

1e6 primes-upto stack.

Try it online!

• 1e6 primes-upto Get a list of primes up to a million
• stack. Prettyprint each element of a sequence, one per line

Answer 28

C (gcc), 59 bytes

i;main(n){for(;n<1e6;i||printf("%d ",n))for(i=n++;n%i--;);}

Try it online! (upto 1000)

Answer 29

CellTail, 165 bytes

I=-1;O=N;N,-1,N:N,(1,1,1),N;999999..,N,N:N,N,N;A,(a,a,b),N:N,a,a+1;A,(a,b,0),N:N,(a+1,2),N;A,(a,b),N:N,(a,b,a%b),N;A,(a,b,c),N:N,(a,b+1,a%(b+1)),N;a,N,N:N,(a,1,a),N;

Should eventually produce the correct output, will take a very long time though.

Try it online

Try it online, numbers up to 1000 so it will actually complete in a few minutes

Answer 30

Arturo, 34 bytes

loop 1..1e6=>[if prime?<=&->print]

Try it