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

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 2

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 3

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 4

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 5

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 6

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

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 8

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 9

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 10

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 11

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 12

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 13

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 14

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 15

Stata, 21 bytes

primes 1000000, clear

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

Answer 16

(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/[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.

Answer 17

Ruby, 60 bytes

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

see here for explanation

Answer 18

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 19

Stax, 7 bytes^CP437

ç►╪(Æ;Ç

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 20

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 21

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 22

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 23

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)