# These Primes of Mine Are Always Solid Lines

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.

• I don't get how does it determine prime number – Filip Bartuzi Aug 29 '14 at 2:38
• @FilipBartuzi Maybe check out en.wikipedia.org/wiki/Sieve_of_Eratosthenes – user31074 Aug 29 '14 at 2:51
• "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? – algorithmshark Aug 29 '14 at 2:52
• 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. – Dennis Aug 29 '14 at 4:12
• 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. – Casey Chu Aug 29 '14 at 5:19

# CJam, 3328 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

• I'll post an explanation when I'm done golfing. – Dennis Aug 29 '14 at 2:47
• 33 bytes and you're not done golfing?? – user31074 Aug 29 '14 at 2:48

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


• That looks like it should be a fractal... – Beta Decay Aug 29 '14 at 10:00
• Remove the space within the ternary before the ' '. It probably messes up your syntax highlighter, but it still works properly. Also, a%b<1 – Value Ink Apr 11 '16 at 17:36
• *'' 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. – histocrat Apr 11 '16 at 20:22

# 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)
'_ '{~0=                    NB. space if cell=0 else underscore


What it looks like:

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


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

• You can replace i>j>1and i%j<1 with i>j>1>i%j – seequ Aug 29 '14 at 10:41
• @Sieg: Cool! It's actually my first time exploiting these concatenated comparisons. – Falko Aug 29 '14 at 11:48
• 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. – xnor Aug 29 '14 at 21:13
• Actually, I think (not tested) you can do i%j<1. It implies i>=j. – seequ Aug 30 '14 at 8:27
• @Sieg: Yes, but we need i>j, not i>=j to avoid blanks on the diagonal. – Falko Aug 30 '14 at 8:29

## 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.
• Apparently 28 is the magic golfing number here. – user31074 Aug 29 '14 at 6:50

## 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))}  • 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 ||. – Dennis Aug 29 '14 at 4:51 • @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. – Todd Lehman Aug 29 '14 at 5:07
• 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==$_?_:$". – Dennis Aug 29 '14 at 5:13
• @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. – Todd Lehman Aug 29 '14 at 6:23

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


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

• 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;). – Dennis Aug 29 '14 at 5:03