12
\$\begingroup\$

Let's create a N×N grid of spaces and underscores that can be used to visually determine if a number is prime. (N may be any positive integer.)

This grid has three simple rules:

  1. The nth column contains the repeated pattern of n - 1 underscores followed by one space. This pattern starts at the first row and is stopped, possibly mid-pattern, at row N. (Rows and columns are 1-indexed.)
  2. The first column is replaced with all underscores instead of all spaces.
  3. If a space occurs somewhere the row index equals the column index it is replaced with an underscore.

Example: N = 10

           1
  1234567890 <-- column indices
 1__________
 2__________
 3__________
 4_ ________
 5__________
 6_  _______
 7__________
 8_ _ ______
 9__ _______
10_ __ _____
 ^ row indices

The indices are just for clarity. The plain grid itself (what your program must output) is:

__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____

Notice that:

  • The first column is all underscores.
  • The second column goes underscore space, underscore space, etc., except for the underscore on row 2.
  • The third column goes underscore underscore space, underscore underscore space, etc., except for the underscore on row 3.
  • etc.

Also notice that besides 1, only prime numbered rows have underscores in every column.

Since underscores span the entire font width, each prime numbered row forms a continuous solid line. So checking if a number is prime or not is quite easy visually; just check if its line is solid across all columns. (In fact looking up to the square root of the row index suffices but outputting that grid seems less elegant.)

Program

Write a program that will draw these grids given N via stdin (or closest alternative). Output goes to stdout (or closest alternative) and should only contain spaces, underscores, and newlines, with an optional trailing newline.

The shortest code wins.

Improve this question
\$\endgroup\$
9
  • \$\begingroup\$ I don't get how does it determine prime number \$\endgroup\$
    – Filip Bartuzi
    Aug 29, 2014 at 2:38
  • 5
    \$\begingroup\$ @FilipBartuzi Maybe check out en.wikipedia.org/wiki/Sieve_of_Eratosthenes \$\endgroup\$
    – user31074
    Aug 29, 2014 at 2:51
  • \$\begingroup\$ "The nth column contains the repeated pattern of n - 1 underscores followed by one space." So shouldn't column n=1 be all spaces, not all underscores? \$\endgroup\$
    – algorithmshark
    Aug 29, 2014 at 2:52
  • 6
    \$\begingroup\$ I must say I don't particularly like the "no trailing newline" requirement. This is very difficult in some languages, downright impossible in others and it only affects programs that print to STDOUT. \$\endgroup\$
    – Dennis
    Aug 29, 2014 at 4:12
  • 4
    \$\begingroup\$ The description was hard for me to understand. This is how I would describe it: Start with a grid of N lines of N underscores. For the nth line, make the kth character a space if k is a divisor of m that isn't 1 or m. \$\endgroup\$
    – Casey Chu
    Aug 29, 2014 at 5:19

8 Answers 8

Reset to default
7
\$\begingroup\$

CJam, 33 28 27 bytes

q~,:)_f{f{md\1=+'_S?}0'_tN}

Try it online.

How it works

q~        " Read one line from STDIN and evaluate it.                                     ";
,:)       " For “N”, push [ 1 ... N ].                                                    ";
_         " Push a copy.                                                                  ";
f{        " For each “I in [ 1 ... N ], push “I   [ 1 ... N ]”; then:                     ";
  f{      " For each “J in [ 1 ... N ], push “J   I”; then:                               ";
    md\   " Push “J % I   J / I”.                                                         ";
    1=+   " Calculate “J % I + (J / I == 1)”.                                             ";
    '_S?  " Push an underscore if the result is truthy and a space otherwise.             ";
  }       "                                                                               ";
  0'_t    " Replace the first character of the resulting array by an underscore.          ";
  N       " Push a newline.                                                               ";
}         "                                                                               ";

Example run

$ cjam solid-primes.cjam <<< 10
__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____
$ cjam solid-primes.cjam <<< 100 | md5sum # trailing newline
e4396b316989813dada21141b569ccf9  -
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I'll post an explanation when I'm done golfing. \$\endgroup\$
    – Dennis
    Aug 29, 2014 at 2:47
  • 9
    \$\begingroup\$ 33 bytes and you're not done golfing?? \$\endgroup\$
    – user31074
    Aug 29, 2014 at 2:48
5
\$\begingroup\$

Ruby, 77 73 characters

puts (1..n=gets.to_i).map{|a|?_+(2..n).map{|b|a!=b&&a%b==0? ' ':?_}.join}

Some tricks I used:

  • The .. operator has almost the lowest precedence of all operators in Ruby, so (1..n=gets.to_i) just works.

  • Instead of adding an extra a!=1 condition when checking to see if the character should be a space instead of an underscore (since the first row is all underscores), I just started the range from 2 and prepended an extra ?_.

  • Line A can become line B:

    A | a%b==0&&a!=b ? ' ':?_
B | a!=b&&a%b==0? ' ':?_

    because I have to have an extra space between b and ? in line A, but that's not needed between 0 and ? in line B. b? is a valid Ruby method, but 0? is not.

  • puts will automatically join arrays with newlines for you, removing the need for an extra *"\n".

Output for n=100:

____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
_ __________________________________________________________________________________________________
____________________________________________________________________________________________________
_  _________________________________________________________________________________________________
____________________________________________________________________________________________________
_ _ ________________________________________________________________________________________________
__ _________________________________________________________________________________________________
_ __ _______________________________________________________________________________________________
____________________________________________________________________________________________________
_   _ ______________________________________________________________________________________________
____________________________________________________________________________________________________
_ ____ _____________________________________________________________________________________________
__ _ _______________________________________________________________________________________________
_ _ ___ ____________________________________________________________________________________________
____________________________________________________________________________________________________
_  __ __ ___________________________________________________________________________________________
____________________________________________________________________________________________________
_ _  ____ __________________________________________________________________________________________
__ ___ _____________________________________________________________________________________________
_ ________ _________________________________________________________________________________________
____________________________________________________________________________________________________
_   _ _ ___ ________________________________________________________________________________________
____ _______________________________________________________________________________________________
_ __________ _______________________________________________________________________________________
__ _____ ___________________________________________________________________________________________
_ _ __ ______ ______________________________________________________________________________________
____________________________________________________________________________________________________
_  _  ___ ____ _____________________________________________________________________________________
____________________________________________________________________________________________________
_ _ ___ _______ ____________________________________________________________________________________
__ _______ _________________________________________________________________________________________
_ ______________ ___________________________________________________________________________________
____ _ _____________________________________________________________________________________________
_   _ __ __ _____ __________________________________________________________________________________
____________________________________________________________________________________________________
_ ________________ _________________________________________________________________________________
__ _________ _______________________________________________________________________________________
_ _  __ _ _________ ________________________________________________________________________________
____________________________________________________________________________________________________
_  __  ______ ______ _______________________________________________________________________________
____________________________________________________________________________________________________
_ _ ______ __________ ______________________________________________________________________________
__ _ ___ _____ _____________________________________________________________________________________
_ ____________________ _____________________________________________________________________________
____________________________________________________________________________________________________
_   _ _ ___ ___ _______ ____________________________________________________________________________
______ _____________________________________________________________________________________________
_ __ ____ ______________ ___________________________________________________________________________
__ _____________ ___________________________________________________________________________________
_ _ ________ ____________ __________________________________________________________________________
____________________________________________________________________________________________________
_  __ __ ________ ________ _________________________________________________________________________
____ _____ _________________________________________________________________________________________
_ _ __  _____ _____________ ________________________________________________________________________
__ _______________ _________________________________________________________________________________
_ __________________________ _______________________________________________________________________
____________________________________________________________________________________________________
_     ___ _ __ ____ _________ ______________________________________________________________________
____________________________________________________________________________________________________
_ ____________________________ _____________________________________________________________________
__ ___ _ ___________ _______________________________________________________________________________
_ _ ___ _______ _______________ ____________________________________________________________________
____ _______ _______________________________________________________________________________________
_  __ ____ __________ __________ ___________________________________________________________________
____________________________________________________________________________________________________
_ _ ____________ ________________ __________________________________________________________________
__ ___________________ _____________________________________________________________________________
_ __ _ __ ___ ____________________ _________________________________________________________________
____________________________________________________________________________________________________
_   _ _  __ _____ _____ ___________ ________________________________________________________________
____________________________________________________________________________________________________
_ __________________________________ _______________________________________________________________
__ _ _________ _________ ___________________________________________________________________________
_ _ ______________ __________________ ______________________________________________________________
______ ___ _________________________________________________________________________________________
_  __ ______ ____________ ____________ _____________________________________________________________
____________________________________________________________________________________________________
_ _  __ _ _____ ___ ___________________ ____________________________________________________________
__ _____ _________________ _________________________________________________________________________
_ ______________________________________ ___________________________________________________________
____________________________________________________________________________________________________
_   _  ____ _ ______ ______ _____________ __________________________________________________________
____ ___________ ___________________________________________________________________________________
_ ________________________________________ _________________________________________________________
__ _________________________ _______________________________________________________________________
_ _ ___ __ __________ _____________________ ________________________________________________________
____________________________________________________________________________________________________
_  _  __  ____ __ ___________ ______________ _______________________________________________________
______ _____ _______________________________________________________________________________________
_ _ __________________ ______________________ ______________________________________________________
__ ___________________________ _____________________________________________________________________
_ ____________________________________________ _____________________________________________________
____ _____________ _________________________________________________________________________________
_   _ _ ___ ___ _______ _______ _______________ ____________________________________________________
____________________________________________________________________________________________________
_ ____ ______ __________________________________ ___________________________________________________
__ _____ _ _____________________ ___________________________________________________________________
_ _  ____ _________ ____ ________________________ __________________________________________________

Now including Extra-Special™ Mega-Colorful Red© Highlight-Magic™® Extended Edition©: (click thumbnail to enlarge)

Ruby with color, 110 characters

puts (1..n=gets.to_i).map{|a|x=(2..n).map{|b|a!=b&&a%b==0? ' ':?_}.join;x.index(' ')??_+x :"\e[41m_#{x}\e[0m"}

Extended Edition

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ That looks like it should be a fractal... \$\endgroup\$
    – Beta Decay
    Aug 29, 2014 at 10:00
  • \$\begingroup\$ Remove the space within the ternary before the ' '. It probably messes up your syntax highlighter, but it still works properly. Also, a%b<1 \$\endgroup\$
    – Value Ink
    Apr 11, 2016 at 17:36
  • \$\begingroup\$ *'' will work the same as join, and you can check for a<b instead of a!=b since no factor of a is greater than a. There might also be savings from slicing into a two-character string with the result of some math on a and b instead of using a ternary. \$\endgroup\$
    – histocrat
    Apr 11, 2016 at 20:22
5
\$\begingroup\$

J - 28 char

1('_ '{~0==+&|:1&=+|/~)@:+i.

Explained by explosion:

1(                    )@:+i.  NB. on vector 1..n, do
                   |/~        NB. take the table "column modulo row"
               1&=+           NB. add 1 to column 1
          =                   NB. identity matrix of size 10
            &|:               NB. transpose both tables (now table is row mod col)
           +                  NB. add them
  '_ '{~0=                    NB. space if cell=0 else underscore

What it looks like:

   1('_ '{~0==+&|:1&=+|/~)@:+i.25
_________________________
_________________________
_________________________
_ _______________________
_________________________
_  ______________________
_________________________
_ _ _____________________
__ ______________________
_ __ ____________________
_________________________
_   _ ___________________
_________________________
_ ____ __________________
__ _ ____________________
_ _ ___ _________________
_________________________
_  __ __ ________________
_________________________
_ _  ____ _______________
__ ___ __________________
_ ________ ______________
_________________________
_   _ _ ___ _____________
____ ____________________
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Python 2, 76 71

r=range(1,input()+1)
for i in r:print''.join("_ "[i%j<1<j<i]for j in r)

Not sure if it can get any shorter than this... These keywords: range, input and print cost quite a lot.

Improve this answer
\$\endgroup\$
6
  • 3
    \$\begingroup\$ You can replace i>j>1and i%j<1 with i>j>1>i%j \$\endgroup\$
    – seequ
    Aug 29, 2014 at 10:41
  • \$\begingroup\$ @Sieg: Cool! It's actually my first time exploiting these concatenated comparisons. \$\endgroup\$
    – Falko
    Aug 29, 2014 at 11:48
  • \$\begingroup\$ I had written this exact code character-for-character up to var names, including the i%j<1<j<i :-P. So maybe it really doesn't get any shorter. \$\endgroup\$
    – xnor
    Aug 29, 2014 at 21:13
  • \$\begingroup\$ Actually, I think (not tested) you can do i%j<1. It implies i>=j. \$\endgroup\$
    – seequ
    Aug 30, 2014 at 8:27
  • \$\begingroup\$ @Sieg: Yes, but we need i>j, not i>=j to avoid blanks on the diagonal. \$\endgroup\$
    – Falko
    Aug 30, 2014 at 8:29
3
\$\begingroup\$

APL (28)

'_ '[(1+(1≠⊢)∧≠∧0=|⍨)/¨⍳2⍴⎕]

Explanation:

  • ⍳2⍴⎕: read a number N and make an N-by-N coordinate matrix
  • (...)/¨: for each pair of coordinates, apply the following function:
    • A cell must have a space if:
    • 0=|⍨: y mod x = 0, and
    • ≠: x isn't equal to y, and
    • 1≠⊢: x isn't 1.
    • 1+: Add 1 to the resulting bit matrix because APL arrays start at 1.
  • '_ '[...]: replace each 1 with an underscore and 2 with a space.
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Apparently 28 is the magic golfing number here. \$\endgroup\$
    – user31074
    Aug 29, 2014 at 6:50
2
\$\begingroup\$

Perl,   69   61

Updated version (thanks, Dennis!)

$n=<>;for$i(1..$n){say"_".join"",map{$i%$_|$i==$_?_:$"}2..$n}

Original version:

$n=<>;for$i(1..$n){say"_".join("",map{$i%$_||$i==$_?"_":" "}(2..$n))}
Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ 1. Neither join nor 2..$n need parentheses. 2. With the -n switch, you can use $_ instead of $n. 3. _ is a valid bareword, so it doesn't need quotes. 4. You can use $" instead of " ". 5. You can use | instead of ||. \$\endgroup\$
    – Dennis
    Aug 29, 2014 at 4:51
  • \$\begingroup\$ @Dennis — Thanks! I applied a few of those. I didn't do the -n thing because I wanted to keep it a self-contained program and not have to say $^N=1. The use of _ as a bareword worked in the case of $i==_ but didn't work in the case of $i%_ because the parser thought %_ was a hash. \$\endgroup\$
    – Todd Lehman
    Aug 29, 2014 at 5:07
  • 1
    \$\begingroup\$ 1. You can keep it self-contained with a shebang (#!/bin/perl -n is usually counted as 1 byte), but that's obviously up to you. I have no idea what $^N=1 does... 2. $i==_ won't work properly; it will test if $i == "_". What I meant is using _ instead of "_", i.e., say _ and $i==$_?_:$". \$\endgroup\$
    – Dennis
    Aug 29, 2014 at 5:13
  • \$\begingroup\$ @Dennis — ohhhh crap, you're right. The edit I made introduced a diagonal line through the matrix. Shame on me for not catching that. Fixed. I see what you mean about _ = "_" now. Unfortunately, it works in the latter case but gives me an error next to the say because it seems to think it's a filehandle. \$\endgroup\$
    – Todd Lehman
    Aug 29, 2014 at 6:23
2
\$\begingroup\$

CJam, 27 bytes

q~:I,{__I?'_*S+I*I<'_t}%zN*

Try it online.

This approach achieves the same byte count as my other answer, but I thought it was worth posting anyway. Instead of marking proper multiples in every row, it does exactly what the specification says.

How it works

q~:I                         " Read an integer I from STDIN.                              ";
    ,{                }%     " For each J ∊ {1,...,I}:                                    ";
          '_*S+              " Push J - 1 underscores followed by a space.                ";
               I*I<          " Repeat the pattern to complete I characters.               ";
       _I?                   " For the first row, replace all spaces with underscores.    ";
      _            '_t       " Replace the Jth character by an underscore.                ";
                        zN*  " Transpose rows and columns; separate with linefeeds.       ";

Example run

$ cjam prime-lines.cjam <<< 10; echo
__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____
$ cjam prime-lines.cjam <<< 100 | md5sum # no trailing newline
83c7b974e1510f482322456a9dbb461f  -
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

C, 143

C is obviously not the right choice of language for this. But for completeness, here's one possible way to do it in C. Works for values of n up to 1048575. Reads n from standard input.

#include <stdio.h>
main(){int n,i=0,j;scanf("%d",&n);char x[1<<20];x[n+1]=0;
for(;++i<=n;){for(j=0;++j<=n;)x[j]=i%j|i==j|j==1?95:32;puts(x+1);}}

It is very fast, however.

  • Runtime for n=1,000,000 (which produces a 1,000,000,000,000-element grid) is approximately 55 minutes on my system.

  • Runtime for n=1000 (which produes a 1,000,000-element grid) is less than 1/100 second.

Improve this answer
\$\endgroup\$
1
  • 4
    \$\begingroup\$ 1. The include is not needed for some compilers (e.g., GCC), so you can remove it. 2. Global variables initialize to 0 and default to int, so you can use char x[1<<20];n,i,j;main.... 3. for(scanf("%d",&n);i++<n;) saves two bytes over scanf("%d",&n);for(;++i<=n;). \$\endgroup\$
    – Dennis
    Aug 29, 2014 at 5:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.