title: List of primes under a million

text:
# Question
Title: List of primes under a million
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
> 42 votes
## 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
> 33 votes
### *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
> 26 votes
## 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
> 23 votes
### 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
> 20 votes
## 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
> 16 votes
## 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
> 11 votes
# 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
> 10 votes
# 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 votes
# Ruby 34

```
require'prime';p Prime.take 78498

```

# Answer
> 9 votes
# 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
> 9 votes
# Haskell, 51

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

```

# Answer
> 9 votes
# 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
> 8 votes
### Ruby ~~50~~ 41

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

```

# Answer
> 8 votes
## APL, 15

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

```

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

# Answer
> 8 votes
# 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
> 8 votes
# Julia, 11

```
primes(10^6)

```

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

# Answer
> 7 votes
# 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
> 6 votes
# gs2, 5 bytes

Encoded in CP437:

```
∟)◄lT

```

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

# Answer
> 5 votes
## 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
> 5 votes
# 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
> 5 votes
# NARS2000 APL, 7 characters

```
⍸0π⍳1e6

```

# Answer
> 4 votes
## 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
> 4 votes
# 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
> 4 votes
# CJam - 11

```
1e6,{mp},N*

```

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

# Answer
> 4 votes
# 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
> 4 votes
# 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
> 3 votes
# 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
> 3 votes
# 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
> 3 votes
## 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
> 3 votes
# Mathematica 25

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

```
Prime@Range@PrimePi[10^6]

```

# Answer
> 3 votes
# 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
> 3 votes
# 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.

# Answer
> 3 votes
## 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
> 3 votes
# 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 votes
# 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
> 3 votes
# 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
> 3 votes
# 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 `0`s 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
> 3 votes
# 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
> 3 votes
# 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
> 2 votes
## 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
> 2 votes
## 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
> 2 votes
# Haskell, 65 chars

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

```

# Answer
> 2 votes
# Octave, ~~12~~, 11

```
primes(1e6)

```

Write 1000000 as 1e6

# Answer
> 2 votes
# 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
> 2 votes
# 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
> 2 votes
# 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
> 2 votes
## 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
> 2 votes
# 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
> 2 votes
# MATL, 5 bytes

```
1e6Zq

```

Explanation:

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

```

# Answer
> 2 votes
# 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
> 2 votes
# 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
> 2 votes
# 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
> 2 votes
# 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
> 2 votes
# 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
> 2 votes
# Japt `-R`, 6 bytes

```
L³õ fj

```

Test it

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

```

# Answer
> 2 votes
# Vyxal, 4 bytes

```
k4'æ

```

Try it Online!

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

```

# Answer
> 2 votes
# 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
> 1 votes
# 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
> 1 votes
# 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
> 1 votes
## 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))))))))

```

# Answer
> 1 votes
# Matlab (12)

Pretty simple=)

```
primes(1e6)'

```

# Answer
> 1 votes
# 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
> 1 votes
**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
> 1 votes
# 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
> 1 votes
## 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
> 1 votes
## 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
> 1 votes
## 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
> 1 votes
## 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
> 1 votes
# 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
> 1 votes
# Perl, 75

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

```

# Answer
> 1 votes
# 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
> 1 votes
# Jagl Alpha 1.2 - 14 bytes

**Not competing, language is younger than question**

```
1e6r{m}%{PZp}/

```

Prints on separate lines.

# Answer
> 1 votes
**Ruby ~~37~~ 32**

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

```

# Answer
> 1 votes
## 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
> 1 votes
## Sage, 28 bytes

```
for i in primes(1e6):print i

```

Try it online

# Answer
> 1 votes
# 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
> 1 votes
# 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
> 1 votes
# 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!<br>~~  ~~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<br>---

tcl, 201 My still not golfed answer:<br>```
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
> 1 votes
### 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
> 1 votes
# 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
> 1 votes
## 05AB1E, 7 bytes

Since there is not yet an answer in 05AB1E.

```
T6mGNp–

```

Try it online!

# Answer
> 1 votes
# 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
> 1 votes
# 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
> 1 votes
# 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
> 1 votes
# 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
> 1 votes
# 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 `9`s off the second line to have it complete in a sane amount of time.

# Answer
> 1 votes
# 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
> 1 votes
# 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
> 1 votes
# 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
> 1 votes
# Arturo, 34 bytes

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

```

Try it

# Answer
> 0 votes
# 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...

# Answer
> 0 votes
# 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

```

# Answer
> 0 votes
## 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).

# Answer
> 0 votes
# (M)AWK - 104 103 100 98 97 87

```
BEGIN{for(n=2;n<1e6;){if(n in L)p=L[n]
else print p=n
for(N=p+n++;N in L;)N+=p
L[N]=p}}

```

---

Old:

The 'x' file:

```
BEGIN{for(n=2;n<1e6;){if(n in L){p=L[n]
del L[n]}else print p=n
for(N=p+n++;N in L;)N+=p
L[N]=p}}

```

The size:

```
$ wc -c x
97 x

```

The run (counting output lines instead of wasting space here) on a Thinkpad T60/T5500@1.6GHz in powersave mode (1 GHz clock, Debian6):

```
$ time mawk -f x | wc -l
78498

real    0m3.894s
user    0m3.820s
sys     0m0.072s

```

But since this won't be the shortest solution, speed is no matter.

The algorithm is a reorganized sieve method. I have not seen this method elsewhere up to now and the local name is "floating sieve of erathosthenes" (FSOE) until I know better.

# Answer
> 0 votes
# 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.

# Answer
> 0 votes
## 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.

# Answer
> 0 votes
# 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)}

```

# Answer
> 0 votes
**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.

# Answer
> 0 votes
# \>\<\> (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.

# Answer
> 0 votes
# 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

# Answer
> 0 votes
# 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

```

# Answer
> 0 votes
# 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.

# Answer
> 0 votes
# Molecule (v6+), 19 bytes

```
0{1+_p?~}u1000000L

```

Explanation:

```
0{1+_p?~}u1000000L
0{1+_p?~}          Push 0, add a code block.
         u1000000  Push one million.
                 L Repeat the code block 1000000 times.

```

# Answer
> 0 votes
# Oracle SQL 11.2, 139 bytes

```
WITH v AS(SELECT LEVEL i FROM DUAL CONNECT BY LEVEL<=:1)SELECT a.i FROM v a, v b GROUP BY a.i HAVING:1-2=SUM(SIGN(MOD(a.i,b.i)))ORDER BY 1;

```

# Answer
> 0 votes
# Java 107 Bytes, 26 minutes, naive approach

```
y->{int i=1,j,n,r=0;for(j=2,n=1000000;(r+=++i>=j?1:0)!=n;j+=j%i==0?i=1:0)System.out.print(i>=j?j+"\n":"");}

```

ungolfed

```
                y->{
                int i=1,j,n,r=0;
                for(j=2,n=1000000;
                    (r+=((++i>=j)?1:0))!=n;
                    j+=((j%i==0)?i=1:0)) {
                    System.out.print(i>=j?j+"\n":"");
                }
                }

```

Worstcase Runtime is `O(n)` divisons for primes as it tests everything in `[2,i[` and looks if anything divides `i` and prints it if it's divisorless or continues if a divisor is found. `n*O(n)` would make it `O(n^2)`, but due to distribution of divisors and primes, it is something along `O(n^2/log(n))+O(n*log(n))` divisons. In practice this takes something along 26 minutes apparently.

# Java ungolfed 1601 Bytes, adaptive wheel sieve, 1.6 seconds

```
public class Sieve {
    ArrayList<Integer> primes = new ArrayList<>();
    ArrayList<Integer> candidates = new ArrayList<>();
    int target = Integer.MAX_VALUE;
    int product = 1;
    int nextEvolve = 0;
    int multiplier = 1;
    int iteration = 0;
    boolean evolve = true;
    Sieve(int n) {
        this.candidates.add(1);
        this.target = n;
    }
    int next() {
        final int toTest = this.product*this.multiplier+this.candidates.get(this.iteration);
        //System.out.println("try: "+toTest+" p:"+this.product+" m:"+this.multiplier+" i:"+this.iteration);
        for(int i = this.nextEvolve; i < this.primes.size() && toTest/this.primes.get(i)>=this.primes.get(i); ++i) {
            if(toTest%this.primes.get(i)==0) {
                ++this.iteration;
                if((this.iteration%=this.candidates.size())==0) {
                    ++this.multiplier;
                }
                return this.next();
            }
        }
        this.primes.add(toTest);
        ++this.iteration;
        if((this.iteration%=this.candidates.size())==0) {
            ++this.multiplier;
            if(this.evolve && this.multiplier%this.primes.get(this.nextEvolve)==0) {
                if(this.target/this.product<toTest) {
                    this.evolve = false;
                }else {
                    final int size = this.candidates.size();
                    for(int i = 1; i < this.primes.get(this.nextEvolve); i++) {
                        for(int j = 0; j < size; j++) {
                            if((i*this.product+this.candidates.get(j))%this.primes.get(this.nextEvolve)!=0) {
                                this.candidates.add(i*this.product+this.candidates.get(j));
                            }
                        }
                    }
                    this.product*=this.primes.get(this.nextEvolve);
                    this.multiplier=this.multiplier/this.primes.get(this.nextEvolve);
                    ++this.nextEvolve;
                }
            }
        }
        return toTest;
    }
    public static void main(String[] args) {
        try {
            System.in.read();
        } catch (final IOException e) {
            e.printStackTrace();
        }
        final Sieve s = new Sieve(1_000_000);
        for(int prime = s.next(); prime < 1_000_000; prime = s.next()) {
            System.out.println(prime);
        }
    }
}

```

# Java golfed 883 Bytes, 16 seconds

```
class S{ArrayList<Integer> p=new ArrayList<>(),c=new ArrayList<>();int t,q,n,m,i;boolean e=true;S(int n){this.c.add(1);this.t=n;q=m=1;n=i=0;}int next(){int toTest=this.q*this.m+this.c.get(this.i);for(int i=this.n;i<this.p.size();++i)if(toTest%this.p.get(i)==0){++this.i;if((this.i%=this.c.size())==0)++this.m;return this.next();}this.p.add(toTest);++this.i;if((this.i%=this.c.size())==0){++this.m;if(this.e && this.m%this.p.get(this.n)==0){if(this.t/this.q<toTest) this.e=false;else{int size=this.c.size();for(int i=1;i<this.p.get(this.n);i++)for(int j=0;j<size;j++)if((i*this.q+this.c.get(j))%this.p.get(this.n)!=0)this.c.add(i*this.q+this.c.get(j));this.q*=this.p.get(this.n);this.m=this.m/this.p.get(this.n);++this.n;}}}return toTest;}public static void main(String[] args){S s=new S(1_000_000);for(int prime=s.next();prime<1_000_000;prime=s.next()){System.out.println(prime);}}}

```

# Answer
> 0 votes
# Pyth, 9 bytes

```
V^T6IP_NN

```

Try it online!

Explanation:

```
V   : Iterate over all numbers from 0 to ...
^T6 : 10^6
I   : If ...
P_N : number is prime ...
N   : print number

```

# Answer
> 0 votes
## Stata, 21 bytes

```
primes 1000000, clear

```

This is (obviously) a built-in command...

# Answer
> 0 votes
# ASMD, 7 bytes

```
W(i|P?p

```

Explanation:

```
W        # Push 1,000,000
 (       # Begin range loop (0 -> 999,999)
  i      # Push counter variable
   |     # Duplicate
    P?p  # If prime, print
       . # Implicit end range loop

```

# Answer
> 0 votes
# Ruby, 60 bytes

```
for n in 0..1e6
if('1'*n)!~/^1?$|^(11+?)\1+$/
puts n
end
end

```

see here for explanation

# Answer
> 0 votes
# Python 2 (PyPy), 86 bytes

```
for i in range(2,int(1e6)):
	if all([i%j!=0 for j in range(2,int(i**0.5)+1)]): print i

```

Try it online!

# Answer
> 0 votes
# Stax, 7 bytes<sup>CP437</sup>

```
ç►╪(Æ;Ç

```

Run and debug online!

## Explanation

Uses the unpacked version to explain.

```
wi|6QVM<
w           loop
 i          loop index `i`
  |6        the `i`th prime
    Q       print and keep on stack
     VM<    while the printed number is less than one million

```

# Answer
> 0 votes
# Microscript II, 18 bytes

```
6E_s{ls1+v;(lP)}*h

```

Requires the latest version of the interpreter due to a bug in how the previous version handled addition with `null` values (although in retrospect it might work even in the previous version if you change `ls1+` to `1sl+`).

Approximate pseudocode translation:

```
x=0
Repeat 10⁶ times:
    x=x+1
    if x is prime:
        print x
End

```

# Answer
> 0 votes
# MathGolf, 5 bytes

```
►rg¶n

```

Try it online.

**Explanation:**

```
►     # Push 1000000
 r    # Pop and push a list in the range [0,1000000)
  g   # Filter it by:
   ¶  #  Is it a prime?
    n # Join with newline delimiter
      # (after which the entire stack is output implicitly as result)

```

---
Tags: code-golf, kolmogorov-complexity, primes
---


title: Find opposite string

text:
# Question
Title: Find opposite string
Your function must accept one string and return the opposite

The opposite string is a string where all characters go in reverse order, all letters are replaced with the opposite mirror letter from the English alphabet and are changed in case, and all digits are replaced with opposite mirror digits

**opposite mirror for letters** means that `a` must be replaced with `z`, `b` must be replaced with `y` and so on. In general let's say we have some letter which index in alphabet is `Index` then it must be replaced with letter which index is `25 - Index` (25 if zero based)

**opposite mirror for digits** means that `0` must be replaced with `9`, `1` must be replaced with `8` and so on. In general let's say we have some digit which index in `0123456789` is `Index` then it must be replaced with digit which index is `9 - Index` (9 if zero based)

If there is a symbol from non English alphabet or digits in string then you don't change it just move to the correct position in reversed string

Input string can contain any printable character. I mean that there also can be Chinese symbols, Arabic symbols, Russian symbols and so on. But all symbols will be printable

**Test cases**:

```
Hello world! --> !WOILD LOOVs

Z 02468 a 13579 A --> z 02468 Z 13579 a

~!@#$%^&*() --> )(*&^%$#@!~

(I) [LOVE] {PROGRAMMING} ,,more,, ..than.. ??10000000000!! --> !!99999999998?? ..MZSG.. ,,VILN,, }tmrnnzitlik{ ]velo[ )r(

By the way мне нравится программировать! --> !ьтавориммаргорп ястиварн енм BZD VSG By

```

The shortest code in each programming language wins!

# Answer
> 8 votes
# MATL, ~~22~~ ~~14~~ 12 bytes

```
P8Y2tP10YSXE

```

Try it at MATL Online

**Explanation**

```
           % Implicitly grab the input as a string
P          % Reverse the input
8Y2        % Push the predefined literal ['0:9', 'A:Z', 'a:z'], a lookup array
t          % Duplicate this array ...
P          % Reverse ...
10YS       % And circularly shift by 10 ...
           % to construct the replacement array ['9:0', 'z:a', 'Z:A']
XE         % Perform the translation
           % Implicitly display the result

```

# Answer
> 6 votes
# Vyxal, 9 7 bytes

\- 2 bytes by AndrovT porting Suevers MATL answer

```
ṘkrḂ₀ǔĿ

```

No questionable constants :p
Try it Online!

**How it works:**

```
ṘkrḂ₀ǔĿ
Ṙ           Reverse string
 krḂ        Bifurcate [0-9A-Za-z], (duplicate and reverse)
    ₀ǔ      Shift string by 10 [9-0z-aZ-A]
      Ŀ     Transliterate

```

# Answer
> 5 votes
# Bash \+ common Linux utils, 53

```
printf -vA %s {Z..A} {9..0}
tr a-z0-9A-Z $A${A,,}|rev

```

Try it online!

# Answer
> 4 votes
# 05AB1E,  ~~9~~  8 bytes

```
RžKÂT._‡

```

Try it online!

Port of Suever's MATL answer.
(Saved a byte by porting it)

#### Explanation

```
RžKÂT._‡  # Implicit input
R         # Reverse
 žK       # Push [a-zA-Z0-9]
   Â      # Bifurcate
    T._   # Shift by 10
       ‡  # Transliterate
          # Implicit output

```

# Answer
> 4 votes
# Pip, 26 bytes

```
RaRXA(Yz.AZ)@(Ry@?_)RXD9-_

```

Try It Online!

Regex-based solution, as pip doesn't have bifurcation (that I could find). Annoyingly, there is no variable for lowercase and uppercase alphabet in pip, so it had to be constructed manually. Explanation:

```
R                       # Reverse
 aR                     # The input regex replaced with
   XA                   # The pattern [A-Za-z]
     (Y                 # Yank (store in variable y) the
       z.AZ)            # alphabetical iterable (a-z + A-Z)
            @(          # at the index of
                @?_)    # the matched character in
              Ry        # the reverse alphabetical iterable
  R                     # Regex replace again with
   XD                   # Regex for digits
     9-_                # Mirrored digit
                        # Implicit output

```

# Answer
> 3 votes
# JavaScript (Node.js),~~77~~ 76 bytes

```
f=([c,...x])=>c?f(x)+Buffer(c).map(t=>t+c>t?57-c:/[a-z]/i.test(c)?187-t:t):x

```

Try it online!

# Answer
> 3 votes
# Python, 86 bytes

```
lambda s:''.join(chr(abs((47<a<58)*105+(96<a|32<123)*187-a))for a in map(ord,s[::-1]))

```

Attempt This Online!

# Answer
> 2 votes
# Python, ~~105~~ 103 bytes

```
lambda s:s.translate([47<c<57and 105-c or(64<c<91or 96<c<123)and 187-c or c for c in range(128)])[::-1]

```

Attempt This Online!

*-2 thanks to @Mukundan314*

# Answer
> 2 votes
# Retina 0.8.2, 15 bytes

```
T`dLld`Ro
O^$`.

```

Try it online! Link includes test cases. Explanation:

```
T`dLld`Ro

```

Transliterate the characters in the string `0..9A..Za..z0..9` to the characters in the reverse of that string.

```
O^$`.

```

Reverse the string.

# Answer
> 2 votes
# Charcoal, 22 bytes

```
≔⪫⪪⭆χι⁵⁺αβθ⭆⮌Ｓ§⁺⮌θι⌕θι

```

Try it online! Link is to verbose version of code. Explanation:

```
≔⪫⪪⭆χι⁵⁺αβθ

```

Build up the transliteration string `01234A..Za..z56789` by taking the digits, splitting into two substrings of length 5, then joining them with the upper and lower case letters.

```
⭆⮌Ｓ§⁺⮌θι⌕θι

```

Map over the reversed input string, finding each character in the transliteration string and looking up the character in the same position in the reversed transliteration string, but with the original character appended so that if it wasn't found then cyclic indexing picks up the original character.

# Answer
> 2 votes
# Factor \+ `spelling`, ~~88~~ 86 bytes

```
[ reverse ALPHABET "0123456789"over >upper glue dup reverse 10 rotate zip substitute ]

```

Try it online!

Port of Suever's MATL answer.

# Answer
> 2 votes
# Python, 86 bytes

```
lambda S:S.translate(dict(zip(A[65:],A[::-1])))[::-1]
*A,=range(123)
A[91:97]=A[48:58]

```

Attempt This Online!

# Answer
> 2 votes
# Zsh `--braceccl --extendedglob`, 86 bytes

```
M=({a-z} {0-9} {A-Z})
<<<${(j..)${(Oas..)1//(#m)?/${M[1+$#M-$M[(Ie)$MATCH]]:-$MATCH}}}

```

Try it online!

Find the `(I)` last index in the array, count from the end to find the replacement, `:-` fallback to the original letter if none was found.

# Answer
> 2 votes
# C (gcc), 135 bytes

In order for UTF-8 characters outside of the ASCII range to not turn into gibberish when reversed I used ICU's functions to iterate the string.

```
#import<unicode/utf8.h>
f(s,i,t)char*s;{i=0;U8_NEXT(s,i,0,t);*s&&f(s+i),isalnum(*s)?putchar(187-82*isdigit(*s)-*s):printf("%.*s",i,s);}

```

Try it online!

Ungolfed:

```
#import<unicode/utf8.h>
f(s,i,t)char*s;{
  i=0;U8_NEXT(s,i,0,t); // Get the next codepoint
  *s&& // Terminate recursion at end of string
  f(s+i), // Run the string in reverse
  isalnum(*s)? // Is [0..9,A..Z,a..z]?
    putchar(187-82*isdigit(*s)-*s): // Yes, invert character
    printf("%.*s",i,s); // Print uninverted codepoint as UTF-8
}

```

# Answer
> 1 votes
# JavaScript, 109 bytes

```
s=>String.fromCharCode(...[...s].reverse().map(c=>/[a-z]/i.test(c,n=c.charCodeAt())?187-n:n<48|n>57?n:105-n))

```

Try it:

```
f=s=>String.fromCharCode(...[...s].reverse().map(c=>/[a-z]/i.test(c,n=c.charCodeAt())?187-n:n<48|n>57?n:105-n))

;[
    'abcdefghijklmnopqrstuvwxyz',
    'Hello world!',
    'Z 02468 a 13579 A',
    '~!@#$%^&*()',
    '(I) [LOVE] {PROGRAMMING} ,,more,, ..than.. ??10000000000!!',
    'By the way мне нравится программировать!'
].forEach(s => console.log(f(s)))
```

# Answer
> 0 votes
# Befunge-98 (FBBI), 136 bytes

```
>]>:88*`v>:68*1-` v
^~v*8f3:_^v`+2*78:_,:!#@_
^<>+\`#v_^>!#v_,:!#@_
v`*8c::<
_7d*\`#v_^v$;>01-*v;
 vf*-10<  <v+**753<
v>2+b*+    >,:!#@_

```

Try it online!

Not a hugely golfed answer, and probably invalid due to lack of handling for Unicode, but a fun exercise!

---
Tags: code-golf, string, number
---


title: Golf my variables (and code)!

text:
# Question
Title: Golf my variables (and code)!
Specifically, this references JavaScript, a programming language that happens to be one you can run on StackExchange/StackOverflow. However, you may use any programming language to do this challenge. **This is not actual JS golfing, but merely a "code-golfable" challenge. Actual complete parsing of JS is not needed.**

An example of JS looks like this (try running all the snippets in here):

```
const constant = 1
var value = 2
for (let i = 0; i < 21; i++) {
    value += constant + value // Addition
}
// Print the value
document.write(value)
```

Problem is, I want my code size to be a bit smaller. So, I could rename the variables to make it look like this:

```
var a = 1
var b = 2
for (let i = 0; i < 21; i++) {
    b += a + b // Addition
}
// Print the value
document.write(b)
```

Notice how the variables have been changed to one letter, and the `const` keyword has been shortened to `var`. Then, we can remove most spaces and all comments:

```
var a=1
var b=2
for (let i = 0; i < 21; i++) {
b+=a+b
}
document.write(b)
```
(Again, this is not "complete" compression, and is just a challenge.)

So, here are the rules (look at the test case; it will make more sense):

* The keywords `const` , `let` , `var` , `while`, and `for` are not variables (notice the spaces!) and should not be changed, with the exception of `const` , which should be changed to `var`  for shortening.
* A variable is defined as the longest string of characters that contain only the characters `0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_$`, not including the rule above. Furthermore, a variable is a variable if and only if one variable is preceded with `const` , `let` , or `var`  (with spaces).
* All variables with the same name must be renamed into a single character variable (one of `abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_$`). All variables with different names must have different values in the result. You may assume that there are no more than 50 unique variables, so only one character is required.
* A single-line comment is all the characters at or after `//`
* All single-line comments should be removed.
* All spaces that are not within keywords must be removed. (Not newlines!)
* **After all of this,** remove any empty lines. This includes comment removal.
* Compact numbers! If a number is an integer, it is defined a number, but with a `.` and all zeros at the end.
* If an integer has more than two zeros, write the number before the final zeros (before the dot), an `e`, then the number of zeros (`30000` to `3e4`, `1515000` to `1515e3`). This is optional for two zeros. While this is not complete, it would be too complicated to compact numbers well.
* You should output all other characters normally.

There is only one test case, but it is a strange one!

## Test case:

```
// Hello world, but stranger!

   // funny spacing

const m = 72000.00 / 1000
var h = String.fromCharCode(m)
  let string = " world!" // Value to print

 var l
for (let i = 1.00000; i < string.length; i++) {
// Number prototype to throw off some lazy variable detection
Number
      console.log(string[i]) // Print each value
   l += string[i]
}
string = string.split("").join("<br>")
 h = l.toUpperCase()

document.write("<!DOCTYPE html><i>" + h.toUpperCase() + "    " + string + "</i>")
```

## Result:

```
var m=72e3/1e3
var h=String.fromCharCode(m)
let s=" world!"
var l
for(let i=1;i<s.length;i++){
Number
console.log(s[i])
l+=s[i]
}
s=s.split("").join("<br>")
h=l.toUpperCase()
document.write("<!DOCTYPE html><i>"+h.toUpperCase()+"    "+s+"</i>")
```

Notice `Number`! This is , so the shortest answer in bytes wins.

# Answer
# 05AB1E, ~~137~~ 134 bytes

```
¶¡ε„//¡нðÚð¡εD'¬¿Qi'¢Ž}.γžj'$«©så}}˜Ćü2εнð«D„¢Ž†³#ð«Qàiyθˆë¨}D¯ÙskDdi®èë\]JõK».γ'.Qyd~}εDdiÐïQiï}D'.å≠iγ`D¨_ig'es}J]JDI‚ε'"¡ιθ€…"ÿ"}`:

```

I/O as a multi-line string.

Some minor notes:

1. The space at `for (` is removed as well, unlike the test cases.
2. Variables that are already a single letter (e.g. `i`) are still counted as any other variable, and therefore replaced with another letter in alphabetical order.
3. Assumes the input JavaScript snippet will never start with a double quote `"`.

Try it online

**Explanation:**

```
¶¡                         # Split the (implicit) multi-line input-string on newlines
  ε                        # Map over each line:
   „//¡                    #  Split it on "//"
       н                   #  Only keep the first value of each list
        ðÚ                 #  Trim any leading/trailing spaces
   ð¡                      #  Then split it by spaces
                           #  (note: builtin `#` fails for lines that are lacking spaces)
     ε                     #  Map over each space-splitted substring:
      D                    #   Duplicate the current substring
       '¬¿Qi   }          '#   If it's equal to dictionary string "const"
            '¢Ž           '#    Push dictionary string "var" instead
      .γ        }          #   Then adjacent group-by the characters of the substring:
        žj                 #    Push builtin string "abc...xyzABC...XYZ012...789_"
          '$«             '#    Append "$"
             ©             #    Store this in variable `®` (without popping)
              s            #    Swap so the current character is at the top
               å           #    Check if this character is in this string
     }                     #  Close the inner map
   ˜                       #  Flatten it to a single list of strings
    Ć                      #  Enclose; append its own head (which we'll discard later)
     ü2                    #  Pop and push its overlapping pairs
       ε                   #  Map over each overlapping pair:
        н                  #   Pop and push the first item of the pair
         ð«                #   Append a space
           D               #   Duplicate it
        „¢Ž†³              #   Push dictionary string "var let"
             #             #   Split it on the space: ["var","let"]
              ð«           #   Append a space to each: ["var ","let "]
                Qài        #   If either is equal to the earlier pushed string:
                   yθ      #    Push the last item of the pair
                     ˆ     #    Pop and add it to the global array
                  ë        #   Else:
                   ¨       #    Remove the appended space again
                  }        #   Close the if-statement
        D                  #   Duplicate the string
         ¯                 #   Push the global array
          Ù                #   Uniquify it
           s               #   Swap so the copy of the string is at the top
            k              #   Get the index of this string in the global array
                           #   (or -1 if it's not in it)
             D             #   Duplicate this index
              di           #   If it's non-negative:
                ®          #    Push variable `®` ("a-zA-Z0-9_$")
                 è         #    Index the index into this string
               ë           #   Else:
                \          #    Discard the index from the stack
  ]                        # Close the open if-else and nested maps
   J                       # Join each inner list back together to a line
    õK                     # Remove any empty lines
      »                    # Join it back by newlines
.γ                         # Adjacent group-by characters again:
  '.Q                     '#  Check if it's equal to a "."
     yd                    #  Check if it's a digit
       ~                   #  OR to check if either of these two is truthy
 }ε                        # After the adjacent group-by: map over the substrings:
   D                       #  Duplicate the current substring
    di                     #  Pop the copy, and if it's an integer:
      Ð                    #   Triplicate it
       ï                   #   Pop one copy, and cast it to an integer
        Qi                 #   Pop the top two, and if their values are the same:
          ï                #    Cast it to an integer
         }D                #   After this if, duplicate the result
           '.å≠i          '#   Pop the copy, and if it does NOT contain a ".":
                γ          #    Group to adjacent equal digits
                 `         #    Pop and push the groups to the stack
                  D        #    Duplicate the last one
                   ¨       #    Remove one of its digits
                    _i     #    If it's 0 (including "00"; "000"; etc.):
                      g    #     Pop and push its length
                       'e '#     Push an "e"
                         s #     Swap the length and "e" on the stack
                     }J    #    After the if-statement: join the stack back together
  ]                        # Close the still open if-statements and map
   J                       # Join everything back together
    D                      # Duplicate the string
     I‚                    # Pair the copy with the input-string
       ε                   # Map over this pair of multi-line strings:
        '"¡               '#  Split it on '"'
           ι               #  Uninterleave it into two parts
            θ              #  Pop and keep the last part
             €             #  Map over each string in this list:
              …"ÿ"         #  Surround it with leading/trailing '"'
       }`                  # After the map: push both lists of strings to the stack
         :                 # Replace them, to fix spaces within double-quotes
                           # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `'¬¿` is `"const"`; `'¢Ž` is `"var"`; and `„¢Ž†³` is `"var let"`.
> 5 votes

# Answer
# Python 3, 501 ~~483 488 492~~ bytes

```
import re
def G(m):b=m.group;return b(1)+f'e{H(b(2))}'+b(3)
E='\n'
I='\\g<1>'
H=len
C='abcdefghijklmnopqrstuvwxyz'
C=[*C,*C.upper(),*'_$']
def S(A):
 s=lambda p,r='':re.sub('(?m)'+p,r,A);A=s('const ','var ');V=re.findall('(?m)(?:let|var) (\w+)\s',A);V.sort(key=H)
 for D in V:A=s(D,C.pop())if~-H(D)else C.remove(D)or A
 A=s('//.*| *$');A=s('^ *');A=s(' ?([=+*\\-\(\)<>/]+) ?',I);A=s(r'(?:\.0+)([^\d])',I);A=s('; +',';');F=A=s(r'(\d)(0+)([^\d])',G);A=s(E*2,E)
 while F!=A:F=A;A=s(E*2,E)
 print(A.strip())

```

Try it online!

I somehow managed to half the number of bytes from when I first started shortening... never done that before
Anyway, I used a lot of regex to replace the strings properly. To test, just make the variable `A` contain the javascript code. Then, at the end, print `A`.

Changes:
-4 bytes by using flag in pattern instead thanks to @Unmitigated
-5 bytes by inlining the for loop thanks to @Julian
+11 bytes to use standard I/O methods. Made this so much uglier and some fixes
> 7 votes

---
Tags: code-golf, javascript
---