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.

• 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. Commented May 26, 2012 at 8:42
• Ah, yes, I was worried about this question being too similar to the plethora of prime number-related questions already around. Commented May 26, 2012 at 8:44
• @GlennRanders-Pehrson Because 10^6 is even shorter ;) Commented May 14, 2014 at 5:20
• 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 Commented Jun 25, 2017 at 21:45
• @ɐɔıʇǝɥʇuʎs How about 1e6 :-D Commented Mar 3, 2018 at 2:09

AWK, 58 bytes

{for(;i++<$0;){for(j=x=1;j<i;)i%++j?J:x++;if(2~x)print i}}  Try it online! Will work for arbitrary amount: echo "1000000" | awk '{for(;i++<$0;){for(j=x=1;j<i;)i%++j?J:x++;if(2~x)print i}}'


or

awk 'END{for(;i++<1e6;){for(j=x=1;j<i;)i%++j?J:x++;if(2~x)print i}}


K (ngn/k), 12 bytes

pri(*/6#10)


Try it online!

pri          Built in prime function
(      )  Change verb to noun
*/6#10   10^6 = 1,000,000


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

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]unionm)
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  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). 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. 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. ><> (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. 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. 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 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)}  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  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.

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;


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.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.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.product*=this.primes.get(this.nextEvolve);
this.multiplier=this.multiplier/this.primes.get(this.nextEvolve);
++this.nextEvolve;
}
}
}
}
public static void main(String[] args) {
try {
} 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);}}}


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


Stata, 21 bytes

primes 1000000, clear


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

(M)AWK - 1041031009897 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/[email protected] 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.

Ruby, 60 bytes

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


see here for explanation

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!

Stax, 7 bytesCP437

ç►╪(Æ;Ç


Run and debug online!

Explanation

Uses the unpacked version to explain.

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


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


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.


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


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)