15
\$\begingroup\$

Given a number N, draw a left aligned NxN board of numbers, leaving 1 blank (as a space) (I will show diagrams with N=5)

   2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

Your job is to construct the Sieve of Eratosthenes, step by step. First, start with 2. It's prime, so leave it there, and replace all other numbers divisible by 2 with the proper number of spaces.

   2  3     5
   7     9    
11    13    15
   17    19   
21    23    25

Next, go to the next unprinted number (3 in this case) and do the same.

   2  3     5
   7          
11    13      
   17    19   
      23    25

And so on, until you reach N.

You need to first print the complete grid, and every time you go to a new number, print the board with the multiples removed. Make sure you print a blank line in between!

Examples

Text in parenthesis () are just for reference, you don't need to print it

N = 2:

  2 (complete grid)
3 4

  2 (remove multiples of 2)
3  

N = 3:

  2 3 (complete grid)
4 5 6
7 8 9

  2 3 (remove multiples of 2)
  5  
7   9

  2 3 (remove multiples of 3)
  5  
7    

Remember, this is , so the code with the smallest number of bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Normally for an N×N sieve you stop sieving after N. \$\endgroup\$ – Neil Oct 19 '16 at 20:40
  • 1
    \$\begingroup\$ For example, if N=10, 100 is not prime, so will be removed at some point. Must all numbers be padded to 3 characters because 100 has 3 digits? \$\endgroup\$ – mbomb007 Oct 19 '16 at 21:05
  • 4
    \$\begingroup\$ Why would you left-align numbers? \$\endgroup\$ – Dennis Oct 19 '16 at 21:22
  • 2
    \$\begingroup\$ Are trailing newlines acceptable? \$\endgroup\$ – Dennis Oct 20 '16 at 2:38
  • 2
    \$\begingroup\$ Are built-in grids allowed? The output will look identical to the example in the post, but will not be a string. \$\endgroup\$ – JungHwan Min Oct 20 '16 at 3:09

12 Answers 12

7
\$\begingroup\$

Jelly, 34 bytes

Ṿ€“1“ ”ys³G
>®i©1ḍoṛ®¦
²R;1©ÇÐĿÑ€Y

Try it online!

How it works

²R;1©ÇÐĿÑ€Y  Main link. Argument: n (integer)

²            Yield n².
 R           Range; yield [1, ..., n²].
   1©        Yield 1 and copy it to the register.
  ;          Append 1 to the range.
             This is the initial state. Let's call it S.
     ÇÐĿ     Call the second helper link until the results are no longer unique.
             This returns all unique results as an array.
        Ṅ€   Call the first helper link on each result.
          Y  Join, separating by linefeeds.

>®i©1ḍoṛ®¦   Second helper link. Argument: S (state)

>®           Compare all integers in S with the value in the register.
  i 1        Find the first index of 1 (i.e., the first number that is greater
             than the register.
   ©         Copy the index to the register. Let's call the index p.
     ḍ       Test all numbers in S for divisibility by p. This yield 1 for
             multiples of p, 0 otherwise.
      o      Logical OR; replace 0's with the corresponding values of S.
       ṛ®¦   Replace the 0 at index p with the corresponding element of S (p).
             For the purposes of the explanation, S is now the updated state.

Ṿ€“1“ ”ys³G  First helper link. Argument: A (array)

Ṿ€           Uneval each; convert all integers in A into strings.
  “1“ ”y     Replace each string "1" with the string " ".
        s³   Split into chunks of length n (command-line argument).
          G  Grid; separate row items by spaces (left-padding since the row items
             are strings), the rows themselves by linefeeds.
\$\endgroup\$
5
\$\begingroup\$

Perl, 250 243 231 202 157 bytes

$n=<>;@a=0..($e=$n*$n);$a[1]=$";for$p(1..$n){next if!$a[$p];for(1..$e){$a[$_]=""if!($p~~[(1,$_)]||$_%$p);printf"%-*s",1+length$e,$a[$_];say""if!($_%$n)}say}

Test the current golf online! (be sure to run as perl -M5.010 main.pl)

The two literal newlines each save 1 byte in place of \n.

Sample output (input of 7):

   2  3  4  5  6  7  
8  9  10 11 12 13 14 
15 16 17 18 19 20 21 
22 23 24 25 26 27 28 
29 30 31 32 33 34 35 
36 37 38 39 40 41 42 
43 44 45 46 47 48 49 

   2  3     5     7  
   9     11    13    
15    17    19    21 
   23    25    27    
29    31    33    35 
   37    39    41    
43    45    47    49 

   2  3     5     7  
         11    13    
      17    19       
   23    25          
29    31          35 
   37          41    
43          47    49 

   2  3     5     7  
         11    13    
      17    19       
   23                
29    31             
   37          41    
43          47    49 

   2  3     5     7  
         11    13    
      17    19       
   23                
29    31             
   37          41    
43          47       

I'm positive I didn't golf it very well, so when I get home I'll take another look at it to see just how much I can shave off.

Edit 1: -7 bytes (changing "print sprintf" to the obvious "printf")

Edit 2: Saved 12 bytes by using $d explicitly in the one place it was called instead of creating a separate variable, by combining some declarations, and by eliminating one of my conditions for the next statement inside the first foreach loop by adding a space somewhere else. An additional 29 bytes were golfed out by reworking two for loops into a single loop, eliminating two variable declarations, and turning unless statements into if-not statements. Declaring my$e=$n*$n; then replacing the three instances of $n*$n with $e (allowing me to drop a paren for one of them) turned out to yield ±0 bytes, but I kept it in anyway.

Edit 3: Thanks to @Dada, another 40 bytes were golfed out (variable declarations, 'foreach' becoming 'for', implicit $_ in several locations, and cutting down on the printf statement size). An additional 1 byte was shaved off by turning if!($c%$p||$c==$p||$p==1) into if!($p~~[(1,$_)]||$_%$p). Unfortunately, the [] around the array is necessary, because the smartmatch operator ~~ is still experimental and doesn't seem to work properly on actual arrays, but does work on references to them instead. 4 more bytes were removed by removing two semicolons and an empty set of quotation marks after the last say.

\$\endgroup\$
  • 1
    \$\begingroup\$ That's a good start, but you can golf it a lot more. Don't declare variables (so don't use my). Use -p flag to have N inside $_ instead of using $n=<>. Write for instead of foreach (this instruction are equivalents). Drop the parenthesis around the condition of the if that are in statement modifier position (for instance if!$c%$n instead of if(!$c%$n). No parenthesis needed to initialize @a : @a=0..$e. You can drop to for variable and $_ wiil be used instead. Write printf"%*s",1+length$e,$a[$c] (the ``sprintf` doc for details about that *) \$\endgroup\$ – Dada Oct 20 '16 at 7:09
  • 1
    \$\begingroup\$ Use $" instead of " ". say"" instead of print"\n" (you have a litteral newline in your code but I can't write it in comment) (you will add to add -M5.010 to the command line, but that doesn't count in the byte count). You can probably use 0..$e=$n*$n to save one byte at the initialisation of $e. Have a look at the perl golfing tips, it contains a lot of usefull tips. But it's nice to see a new perl golfer, welcome! :) (and forgive my spelling mistakes, I may have write my previous comment too fast) \$\endgroup\$ – Dada Oct 20 '16 at 7:18
  • \$\begingroup\$ @Dada Thank you for your advice! I'm not very familiar with running code on the command line (I tend to run it as a file) but I'll take a look at doing it that way. As for if!$c%$n, the ! operator has precedence over the % operator, so technically this would be if((!$c)%$n) which comes out to false for anything other than $c = 0 (which I don't want). As for your other tips, I'll see what I can do! Thank you very much! \$\endgroup\$ – Gabriel Benamy Oct 20 '16 at 13:25
  • \$\begingroup\$ You don't have to run it on the command line, those modifications will work if you put them inside a file as well. Sorry for the !, I wasn't on my computer to check it. You should be able to get down to 160 characters I think. \$\endgroup\$ – Dada Oct 20 '16 at 14:07
5
\$\begingroup\$

PHP, 155 Bytes

for(;$d++<$n=$argv[1];$x&$a[$d]<1?:print"\n".chunk_split(join($a),$n*$l))for($i=$d*$x=$d>1;$n**2>=$i+=$d;)$a[$i]=str_pad($x|$i<2?"":$i,$l=strlen($n**2)+1);

@Crypto -3 Bytes Thank You @Titus -6 Bytes Thank You

Try it

First time that I use print in a after loop condition

Breakdown

for(;$d++<$n=$argv[1];
$x&$a[$d]<1?:print"\n".chunk_split(join($a),$n*$l))
#after loop print the grid if $d = 1 or is prime
for($i=$d*$x=$d>1;$n**2>=$i+=$d;)
$a[$i]=str_pad($x|$i<2?"":$i,$l=strlen($n**2)+1);
#fills the array at first run and replace positions with space in the next runs 

Previous Version 174 Bytes

for(;$d++<=$n=$argv[1];!($d<2||$a[$d]>0)?:print chunk_split(join($a),$n*$l)."\n")for($i=$d<2?1:2*$d;$i<=$m=$n**2;$i+=$d)$a[$i]=str_pad($d<2?($i<2?"":$i):" ",$l=strlen($m)+1);  
\$\endgroup\$
  • 1
    \$\begingroup\$ -3 bytes changing the condition : !($d<2||$a[$d]>0) => $d>1&&$a[$d]<1 \$\endgroup\$ – Crypto Oct 20 '16 at 9:17
  • 1
    \$\begingroup\$ -1 byte using this trick to get integer length $l=strlen($m)+1 to $l=log10($m)+2 \$\endgroup\$ – Crypto Oct 20 '16 at 9:23
  • 1
    \$\begingroup\$ -3 bytes: $i=$d*$x=$d>1 instead of $i=$d<2?0:$d and $x for the other two occurences of $d>1 \$\endgroup\$ – Titus Oct 22 '16 at 17:17
  • 1
    \$\begingroup\$ -2 bytes: $n*$n>=$i+=$d instead of ($i+=$d)<=$m=$n**2 and $n*$n for the other occurence of $m \$\endgroup\$ – Titus Oct 22 '16 at 17:25
  • 1
    \$\begingroup\$ -1 byte: leading instead of trailing newline \$\endgroup\$ – Titus Oct 22 '16 at 17:27
3
\$\begingroup\$

Groovy, 201 195 191 Bytes

{n->a=(1..n*n).toArray();y={a.collect{(it?"$it":"").padRight((""+n*n).size())}.collate(n).each{println it.join(" ")}};a[0]=0;y(a);(2..n).each{b->(b+1..n*n).each{if(it%b==0){a[it-1]=0}};y(a)}}

This is an absolute cluster... The left-align murdered my byte count. But hey, it works. Here's the output for 4:

   2  3  4 
5  6  7  8 
9  10 11 12
13 14 15 16

   2  3    
5     7    
9     11   
13    15   

   2  3    
5     7    
      11   
13         

   2  3    
5     7    
      11   
13         

Ungolfed:

{
    n->
    a = (1..n*n).toArray();                           // Create initial array.
    y = {                                             // Createa  printing utility closure.
        a.collect {                                   // Create an array collection of...
            (it ? "$it":"").padRight((""+n*n).size()) // If 0, store "", else store number & right pad it.
        }.collate(n).each{                            // Collate by n (break into nxn grid).
            println it.join(" ")                      // print each separated by spaces.
        }
    };
    a[0]=0;                                           // Remove first element.
    y(a);                                             // Print initial status.
    (2..n).each{                                      // From 2 to n...
        b->
        (b+1..n*n).each{                              // From current number + 1 to end of grid...
            if(it%b==0){                              // If current grid position is divisible...
                a[it-1]=0                             // Replace with 0.
            }
        }
        y(a)                                          // Print it.
    }        
}

\$\endgroup\$
  • 2
    \$\begingroup\$ This doesn't look left-aligned to me. \$\endgroup\$ – Dennis Oct 20 '16 at 2:38
  • \$\begingroup\$ Fixed... I just didn't get a chance to edit it until now... \$\endgroup\$ – Magic Octopus Urn Oct 20 '16 at 13:34
  • \$\begingroup\$ @Dennis I actually saw your comments and thought he had changed it based on your comment. \$\endgroup\$ – Magic Octopus Urn Oct 20 '16 at 16:24
3
\$\begingroup\$

Perl, 115 114 113 112 bytes

Includes +1 for -a

Run with input number on STDIN:

perl -M5.010 sieving.pl <<< 7

sieving.pl:

#!/usr/bin/perl -a
$_*=$_;$a.="$_"x$|++|$"x"@+".($_%"@F"?$":$/)for/\d+/..$_;*_=a;s^^$$_++||say;$.++;s//$&%$.|$&==$.?$&:$&&$_/eg^eg

Needs a recent enough perl so that -a implies -n. If your perl is too old add a -n option.

Prints a trailing newline which is allowed.

\$\endgroup\$
2
\$\begingroup\$

Python 2, 199 202 201 bytes

+3 bytes (I wasn't stopping early)
-1 byte thanks to @Oliver (missed a space)

def f(n,p={()}):
 m=n*n;g=['']+[[i,''][any(i>n and i%n<1for n in p)]for i in range(2,m+1)];x=min(set(g)-p);i=0
 while i<m+n:print' '.join('%%%ds'%-len(`m`)%v for v in g[i:i+n]);i+=n
 if x<=n:f(n,p|{x})

repl.it

\$\endgroup\$
  • 1
    \$\begingroup\$ You can remove a space between 1 and for \$\endgroup\$ – Oliver Ni Oct 20 '16 at 4:50
2
\$\begingroup\$

JavaScript (ES6), 190 189 bytes

Directly prints to the console.

f=(w,k=1,a=[...Array(w*w)].map((_,n)=>n&&n+1))=>k++<=w&&(k==2|a[k-2]&&console.log(a.map((n,x)=>`${n||''}    `.slice(0,`_${w*w}`.length)+(++x%w?'':`
`)).join``),f(w,k,a.map(n=>n==k|n%k&&n)))

Demo

f=(w,k=1,a=[...Array(w*w)].map((_,n)=>n&&n+1))=>k++<=w&&(k==2|a[k-2]&&console.log(a.map((n,x)=>`${n||''}    `.slice(0,`_${w*w}`.length)+(++x%w?'':`
`)).join``),f(w,k,a.map(n=>n==k|n%k&&n)))

f(5)

\$\endgroup\$
2
\$\begingroup\$

Batch, 464 bytes

@echo off
set/an=%1,s=n*n,t=s,c=1
set p=
:l
set/ac+=1,t/=10
set p= %p%
if %t% gtr 0 goto l
for /l %%i in (1,1,%1)do call:i %%i
exit/b
:i
set l=
set/af=0
call:f %1 %1
if %f%==0 for /l %%j in (1,1,%s%)do call:j %1 %%j
exit/b
:j
set/am=%2,f=!(m-1),g=%2%%n
call:f %1 %2
if %f% gtr 0 set m=
set m=%m% %p%
call set l=%%l%%%%m:~0,%c%%%
if %g%==0 echo(%l%&set l=
if %2==%s% echo(
exit/b
:f
for /l %%l in (2,1,%1)do if %%l neq %2 set/af+=!(%2%%%%l)

This was somewhat laborious. Explanation: Starts by squaring n so that it can calculate the desired column width c, and the appropriate amount of padding p, using the loop :l. The outer loop from 1 to n then runs once for each grid, calling the subroutine :i. First the value is checked to see whether it is 1 or prime; if not then that grid is skipped. The inner loop from 1 to n*n then handles the rows and columns of the grid, calling the subroutine :j. Each value is checked to see whether it is one of the prime numbers found so far, or if none of the prime numbers found so far divide it. If so then the value is concatenated to the output buffer, which is then padded to the desired column width. The buffer is printed and cleared every n lines, and an extra blank line is added at the end of the grid. The :f label denotes the factor-checking subroutine; f(x,y) adds 1 to f for each integer between 2 and x that divides y, excluding y itself.

\$\endgroup\$
2
\$\begingroup\$

R, 195 191 185 204 bytes

f=function(N){a=b=1:N^2;i=1;a[1]="";S=sprintf;while(i<=N){for(j in b)cat(a[j]<-S(S("%%-%is",nchar(N^2)),if(j==i|j%%i|i<2)a[j]else ""),if(j%%N)"" else"\n");cat("\n");i=(grep("\\d",a[-(1:i)],v=T)[1]:1)[1]}}

Thanks to @Billywob for 6 extra bytes saved!

Indented, with newlines:

f=function(N){
   a=b=1:N^2 #Initial array
   i=1 #Turn counter
   a[1]="" #1 never shown
   S=sprintf
   while(i<=N){
      for(j in b)
         cat(a[j]<-S(S("%%-%is",nchar(N^2)),if(j==i|j%%i|i<2)a[j]else ""),
             if(j%%N)"" else"\n") #Newline at end of row
      cat("\n") #Newline between turns
      i=(grep("\\d",a[-(1:i)],v=T)[1]:1)[1] #Select next prime as next i
   }
}

Usage:

> f(2)
  2 
3 4 

  2 
3   

> f(3)
  2 3 
4 5 6 
7 8 9 

  2 3 
  5   
7   9 

  2 3 
  5   
7     

> f(9)
   2  3  4  5  6  7  8  9  
10 11 12 13 14 15 16 17 18 
19 20 21 22 23 24 25 26 27 
28 29 30 31 32 33 34 35 36 
37 38 39 40 41 42 43 44 45 
46 47 48 49 50 51 52 53 54 
55 56 57 58 59 60 61 62 63 
64 65 66 67 68 69 70 71 72 
73 74 75 76 77 78 79 80 81 

   2  3     5     7     9  
   11    13    15    17    
19    21    23    25    27 
   29    31    33    35    
37    39    41    43    45 
   47    49    51    53    
55    57    59    61    63 
   65    67    69    71    
73    75    77    79    81 

   2  3     5     7        
   11    13          17    
19          23    25       
   29    31          35    
37          41    43       
   47    49          53    
55          59    61       
   65    67          71    
73          77    79       

   2  3     5     7        
   11    13          17    
19          23             
   29    31                
37          41    43       
   47    49          53    
            59    61       
         67          71    
73          77    79       

   2  3     5     7        
   11    13          17    
19          23             
   29    31                
37          41    43       
   47                53    
            59    61       
         67          71    
73                79       

> f(12)
    2   3   4   5   6   7   8   9   10  11  12  
13  14  15  16  17  18  19  20  21  22  23  24  
25  26  27  28  29  30  31  32  33  34  35  36  
37  38  39  40  41  42  43  44  45  46  47  48  
49  50  51  52  53  54  55  56  57  58  59  60  
61  62  63  64  65  66  67  68  69  70  71  72  
73  74  75  76  77  78  79  80  81  82  83  84  
85  86  87  88  89  90  91  92  93  94  95  96  
97  98  99  100 101 102 103 104 105 106 107 108 
109 110 111 112 113 114 115 116 117 118 119 120 
121 122 123 124 125 126 127 128 129 130 131 132 
133 134 135 136 137 138 139 140 141 142 143 144 

    2   3       5       7       9       11      
13      15      17      19      21      23      
25      27      29      31      33      35      
37      39      41      43      45      47      
49      51      53      55      57      59      
61      63      65      67      69      71      
73      75      77      79      81      83      
85      87      89      91      93      95      
97      99      101     103     105     107     
109     111     113     115     117     119     
121     123     125     127     129     131     
133     135     137     139     141     143     

    2   3       5       7               11      
13              17      19              23      
25              29      31              35      
37              41      43              47      
49              53      55              59      
61              65      67              71      
73              77      79              83      
85              89      91              95      
97              101     103             107     
109             113     115             119     
121             125     127             131     
133             137     139             143     

    2   3       5       7               11      
13              17      19              23      
                29      31                      
37              41      43              47      
49              53                      59      
61                      67              71      
73              77      79              83      
                89      91                      
97              101     103             107     
109             113                     119     
121                     127             131     
133             137     139             143     

    2   3       5       7               11      
13              17      19              23      
                29      31                      
37              41      43              47      
                53                      59      
61                      67              71      
73                      79              83      
                89                              
97              101     103             107     
109             113                             
121                     127             131     
                137     139             143     

    2   3       5       7               11      
13              17      19              23      
                29      31                      
37              41      43              47      
                53                      59      
61                      67              71      
73                      79              83      
                89                              
97              101     103             107     
109             113                             
                        127             131     
                137     139                     
\$\endgroup\$
  • \$\begingroup\$ Nice, I can never figure out how to properly print matrices to comply to codegolfing requirements never mind left justifying them. You can save a few bytes by though. The exponentiation operator ^ is the only one that isn't vectorized when generating sequences using : which means you can use e.g. 1:2^2 to get 1 2 3 4. Secondly if you define a=b=1:n^2 you can later use for(j in b) instead of defining another vector to loop over. Should save you a couple of bytes. \$\endgroup\$ – Billywob Oct 20 '16 at 15:10
  • \$\begingroup\$ Indeed! Thanks! Can never remember the exact order of operator precedence... \$\endgroup\$ – plannapus Oct 20 '16 at 15:45
  • \$\begingroup\$ Why are there three spaces between the numbers in f(2) and f(3) and two spaces in f(9)? It should always be one space. \$\endgroup\$ – Oliver Ni Oct 20 '16 at 18:36
  • \$\begingroup\$ Oh right I set up 3 characters as the norm because i was testing with N=10, let me correct that. \$\endgroup\$ – plannapus Oct 21 '16 at 6:37
1
\$\begingroup\$

J, 125 bytes

p=:3 :'}."1,./('' '',.>)"1|:(-%:#y)]\((a:"_)`(<@":)@.*)"+y'
3 :'p@>~.|.(]*](*@|~+.=)({[:I.*){])&.>/\.(<"+i.-y),<]`>:@.*i.*:y'

This is explicit, not tacit J, but there should be a way to golf it tacitly.

Usage

   p =: 3 :'}."1,./('' '',.>)"1|:(-%:#y)]\((a:"_)`(<@":)@.*)"+y'
   f =: 3 :'p@>~.|.(]*](*@|~+.=)({[:I.*){])&.>/\.(<"+i.-y),<]`>:@.*i.*:y'
   f 2
  2
3 4

  2
3  
   f 3
  2 3
4 5 6
7 8 9

  2 3
  5  
7   9

  2 3
  5  
7    
   f 4
   2  3  4 
5  6  7  8 
9  10 11 12
13 14 15 16

   2  3    
5     7    
9     11   
13    15   

   2  3    
5     7    
      11   
13         
   f 5
   2  3  4  5 
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

   2  3     5 
   7     9    
11    13    15
   17    19   
21    23    25

   2  3     5 
   7          
11    13      
   17    19   
      23    25

   2  3     5 
   7          
11    13      
   17    19   
      23      
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 133 bytes

Grid[#,Alignment->Left]~Print~"
"&/@FoldList[#/.(##|1&@@(2~r~i#2)->Null)&,(r=Range)[i=#^2]~Partition~#/.Rule[1,],Prime@r@PrimePi@#];&
\$\endgroup\$
1
\$\begingroup\$

PHP, 155 150 147 145 142 140 bytes

for(;$k++<$n=$argv[1];)if($k<2||$a[$k]){for($i=0;$i++<$n*$n;)echo$a[$i]=$k>1?$i>$k&$i%$k<1?"":$a[$i]:($i<2?"":$i),"\t\n"[$i%$n<1];echo"\n";}

breakdown

for(;$k++<$n=$argv[1];)
    if($k<2||$a[$k])    // if first iteration or number unprinted ...
{
    for($i=0;$i++<$n*$n;)
        echo
            $a[$i]=$k>1
                ?$i>$k&$i%$k<1
                    ?""         // sieve
                    :$a[$i]     // or copy value
                :($i<2?"":$i)   // first iteration: init grid
            ,
            // append tab, linebreak every $n columns
            "\t\n"[$i%$n<1]
        ;
    // blank line after each iteration
    echo"\n";
}
\$\endgroup\$
  • 1
    \$\begingroup\$ $a[$i]=""; instead of unset($a[$i]); should save 4 Bytes \$\endgroup\$ – Jörg Hülsermann Oct 22 '16 at 9:44
  • \$\begingroup\$ $i%$k<1 instead of !($i%$k) save one Byte \$\endgroup\$ – Jörg Hülsermann Oct 22 '16 at 16:22

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.