58
\$\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\$
6
  • 13
    \$\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\$ 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\$ May 26 '12 at 8:44
  • 3
    \$\begingroup\$ @GlennRanders-Pehrson Because 10^6 is even shorter ;) \$\endgroup\$ May 14 '14 at 5:20
  • 2
    \$\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\$ Jun 25 '17 at 21:45
  • 2
    \$\begingroup\$ @ɐɔıʇǝɥʇuʎs How about 1e6 :-D \$\endgroup\$
    – Titus
    Mar 3 '18 at 2:09

106 Answers 106

1 2 3
4
0
\$\begingroup\$

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

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.
\$\endgroup\$
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\$
1
  • \$\begingroup\$ Since this language postdates the challenge by nearly 4 years, I've marked this submission as non-competing \$\endgroup\$
    – user45941
    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\$

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

Japt -R, 6 bytes

L³õ fj

Test it

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

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.

\$\endgroup\$
1 2 3
4

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.