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.

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. — Peter Taylor, 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. — Delan Azabani, Commented May 26, 2012 at 8:44
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 — Computronium, Commented Jun 25, 2017 at 21:45

C K · Accepted Answer · 2024-05-23 12:09:35Z

1

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

answered May 23 at 12:09

C K

1114 bronze badges

Add a comment |

C K · Accepted Answer · 2024-06-04 20:15:05Z

1

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

answered Jun 4 at 20:15

C K

1114 bronze badges

Add a comment |

edwkar · Accepted Answer · 2012-06-04 02:07:15Z

0

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

answered Jun 4, 2012 at 2:07

edwkar

212 bronze badges

Add a comment |

Ray · Accepted Answer · 2013-10-29 04:33:14Z

0

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

answered Oct 29, 2013 at 4:33

Ray

2,02612 silver badges17 bronze badges

Add a comment |

Doorknob · Accepted Answer · 2013-11-07 03:33:15Z

0

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

answered Nov 7, 2013 at 3:33

Doorknob

71.7k20 gold badges143 silver badges385 bronze badges

Add a comment |

Michael Easter · Accepted Answer · 2014-05-16 21:30:57Z

0

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.

answered May 16, 2014 at 21:30

Michael Easter

6258 silver badges11 bronze badges

Add a comment |

EvilFonti · Accepted Answer · 2014-07-18 07:32:01Z

0

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.

answered Jul 18, 2014 at 7:32

EvilFonti

3011 silver badge3 bronze badges

Add a comment |

Sp3000 · Accepted Answer · 2015-03-12 14:54:08Z

0

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

edited Mar 12, 2015 at 14:54

answered Mar 12, 2015 at 14:28

Sp3000

61.9k13 gold badges115 silver badges287 bronze badges

Add a comment |

xenia · Accepted Answer · 2015-03-13 18:32:15Z

0

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.

edited Mar 13, 2015 at 18:32

answered Mar 9, 2015 at 11:58

xenia

8,1822 gold badges27 silver badges59 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jul 3, 2015 at 12:37

blabla999

1,97712 silver badges11 bronze badges

Add a comment |

DanaJ · Accepted Answer · 2015-07-04 03:35:44Z

0

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)}

edited Jul 4, 2015 at 3:35

answered Nov 1, 2014 at 5:46

DanaJ

5064 silver badges6 bronze badges

Add a comment |

Vasu Adari · Accepted Answer · 2015-09-03 14:50:21Z

0

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

edited Sep 3, 2015 at 14:50

answered Sep 3, 2015 at 14:40

Vasu Adari

9797 silver badges17 bronze badges

Add a comment |

Hitster GTD · Accepted Answer · 2016-03-26 19:45:23Z

0

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.

answered Mar 26, 2016 at 19:45

Hitster GTD

11 bronze badge

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

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;

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Apr 27, 2016 at 13:51

Jeto

1,7019 silver badges10 bronze badges

Add a comment |

HopefullyHelpful · Accepted Answer · 2016-05-28 07:43:32Z

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);}}}

John Red · Accepted Answer · 2016-05-28 19:57:31Z

0

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

answered May 28, 2016 at 19:57

John Red

1513 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

Stata, 21 bytes

primes 1000000, clear

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 13, 2016 at 16:13

f1rstguess

1911 silver badge4 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

Ruby, 60 bytes

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

see here for explanation

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 2, 2017 at 14:47

Selim

1013 bronze badges

Add a comment |

Husnain Raza · Accepted Answer · 2017-08-12 04:21:03Z

0

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!

answered Aug 12, 2017 at 4:21

Husnain Raza

3691 gold badge3 silver badges10 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 2, 2018 at 17:05

Weijun Zhou

3,65713 silver badges41 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Apr 1, 2019 at 1:11

SuperJedi224

12k1 gold badge45 silver badges68 bronze badges

Add a comment |

emanresu A · Accepted Answer · 2022-09-03 02:33:51Z

0

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.

edited Sep 3, 2022 at 2:33

emanresu A

44.2k5 gold badges100 silver badges240 bronze badges

answered Apr 27, 2016 at 8:40

user47018

Add a comment |

emanresu A · Accepted Answer · 2022-09-04 06:15:45Z

0

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

edited Sep 4, 2022 at 6:15

emanresu A

44.2k5 gold badges100 silver badges240 bronze badges

answered Nov 14, 2016 at 4:47

Oliver Ni

10.6k3 gold badges38 silver badges107 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2022-09-22 08:24:28Z

0

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)

answered Sep 22, 2022 at 8:24

Kevin Cruijssen

131k13 gold badges144 silver badges384 bronze badges

Add a comment |

Stack Exchange Network

List of primes under a million

115 Answers 115

AWK, 58 bytes

K (ngn/k), 12 bytes

Python, 68

Haskell, 126 chars, Using Sieve of Eratosthenes

Ruby, 94 (optimized for speed, 2.655 secs)

Groovy - 65 chars

C# & LinqPad 71

><> (Fish), 54 51 bytes

Smalltalk - 22 characters

Perl, 35

Ruby, 118 117 bytes

Run Time:

Swift 2, 79 bytes

Oracle SQL 11.2, 139 bytes

Java 107 Bytes, 26 minutes, naive approach

Java ungolfed 1601 Bytes, adaptive wheel sieve, 1.6 seconds

Java golfed 883 Bytes, 16 seconds

Pyth, 9 bytes

Stata, 21 bytes

(M)AWK - 104 103 100 98 97 87

Ruby, 60 bytes

Python 2 (PyPy), 86 bytes

Stax, 7 bytes^CP437

Explanation

Microscript II, 18 bytes

Molecule (v6+), 19 bytes

ASMD, 7 bytes

MathGolf, 5 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
kolmogorov-complexity
primes
or ask your own question.

Linked

Hot Network Questions

List of primes under a million

115 Answers 115

AWK, 58 bytes

K (ngn/k), 12 bytes

Python, 68

Haskell, 126 chars, Using Sieve of Eratosthenes

Ruby, 94 (optimized for speed, 2.655 secs)

Groovy - 65 chars

C# & LinqPad 71

><> (Fish), 54 51 bytes

Smalltalk - 22 characters

Perl, 35

Ruby, 118 117 bytes

Run Time:

Swift 2, 79 bytes

Oracle SQL 11.2, 139 bytes

Java 107 Bytes, 26 minutes, naive approach

Java ungolfed 1601 Bytes, adaptive wheel sieve, 1.6 seconds

Java golfed 883 Bytes, 16 seconds

Pyth, 9 bytes

Stata, 21 bytes

(M)AWK - 104 103 100 98 97 87

Ruby, 60 bytes

Python 2 (PyPy), 86 bytes

Stax, 7 bytesCP437

Explanation

Microscript II, 18 bytes

Molecule (v6+), 19 bytes

ASMD, 7 bytes

MathGolf, 5 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Stax, 7 bytes^CP437

Not the answer you're looking for? Browse other questions tagged
code-golf
kolmogorov-complexity
primes
or ask your own question.