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

# 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. # Molecule (v6+), 19 bytes (non-competing) 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.  • Since this language postdates the challenge by nearly 4 years, I've marked this submission as non-competing – user45941 Apr 27 '16 at 9:00 # 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.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);}}}  # 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/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. # ASMD, 7 bytes (non-competing) 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  # Ruby, 60 bytes for n in 0..1e6 if('1'*n)!~/^1?$|^(11+?)\1+\$/
puts n
end
end


see here for explanation

• @WheatWizard thanks, fixed now! Mar 2 '17 at 16:24

# 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


# 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


# 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


# Japt-R, 6 bytes

L³õ fj


Test it

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