56
\$\begingroup\$

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.

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

103 Answers 103

0
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Since this language postdates the challenge by nearly 4 years, I've marked this submission as non-competing \$\endgroup\$ – Mego Apr 27 '16 at 9:00
0
\$\begingroup\$

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;
\$\endgroup\$
0
\$\begingroup\$

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);}}}
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

Stata, 21 bytes

primes 1000000, clear

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

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

Ruby, 60 bytes

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

see here for explanation

\$\endgroup\$
  • \$\begingroup\$ @WheatWizard thanks, fixed now! \$\endgroup\$ – Selim Mar 2 '17 at 16:24
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Stax, 7 bytesCP437

ç►╪(Æ;Ç

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.