Prime Numbers

Prime Numbers is among the hardest challenges in VimGolf. I've spent more time working on this challenge than any other. When I first saw it, I figured I'd have to brush up on my vimscript. As it turns out, you don't really need any at all.

"=r^I543)^MP:%no<S-Tab>~VEEkdYo@0D@.^O@.^MdZZ for 35.

That's the optimized version. It's tricky, but the basics behind it are relatively simple. The algorithm is the sieve of Eratosthenes. It uses range() to set up a list of numbers, one per line, and :%normal to run a macro on each line. Within the :normal, it reads the number on the line, and recursively moves the cursor down that many lines, clearing each one (but not deleting them). Effectively, every number that's a multiple of the number on the line you started from is cleared. At the end, only the primes remain.

Simplified version

"=range(543)^MPqq@0D@qqdj:%normal ~Y@q^M:v/./d^MZZ

• "=range(543)^MP: Using range(x) with one argument returns a list of the numbers in [0,x). By typing it into the expression register's "= command line, you can paste the numbers into the file, one per line. This is the only vimscript we'll use, and it's a common VimGolf trick anyway. (You could use an incrementing macro, but it's slightly slower than range() when fully optimized.)
• @0D@q: The macro to run from each line. The "0 register will be set beforehand to a macro that moves the cursor down some number of lines. We'll be in the first column, so D will clear the line we get to. @q makes the macro recursively call itself until it hits the end of the file.
• dj: Deletes 0 and 1 so they don't get in the way.
• :%normal: Runs its argument as a macro on each line.
• ~: Fails the :normal on blank lines. This is normally the case flipping command, but it has useful macro failing properties. If the rest of the commands ran from blank lines, they would ruin the file. :normal treats failure different from other macros—it stops the current run of the macro, but it starts up again on the next. This means you can use a "failure test" to run commands conditionally... in this case, depending on whether the line is empty.
• Y: Yanks the line the cursor is on. The line itself is a macro. Y yanks the line with the newline (^J) at the end, which is a normal mode command for moving the cursor down. The number on the line acts as a numeric argument to the newline at the end, and together they form a macro to move the cursor down the specified amount. This macro will be yanked into two registers, "" and "0, like any other yank. In the @q macro, D will overwrite "" and "- but leave "0 untouched, so that's what we'll use.
• @q: Run the recursive macro defined earlier. When it runs from the last line, it will fail, which is good, because you don't want your macros running forever. Note that the text Prime Numbers that we started the challenge with will still be there at first. This line acts as a "junk line". You need at least one line after the last prime, so the ^J command doesn't land on a line you don't want to clear.
• :v/./d: Every line that didn't contain a prime number is now blank. This command means "delete every line that doesn't contain a character". It destroys blank lines.

Just one last problem: ~ moves the cursor right a column, and ^J moves straight down, just like j. You'd think we'd sometimes land on the second column when we run D. This turns out not to be an issue though, because:

1. from the number 2, the cursor can't go right anyway, and
2. from every other number, the first ^J will land on a multiple of 2, which will already be blank. Once D runs on the blank line, the cursor will stay on the first column until the end of the file.

Optimize it

"=r^I543)^MP:%no<S-Tab>~VEEkdYo@0D@.^O@.^MdZZ

Using command completion, a bunch of strokes were saved on range() and :normal. The :normal starts with a nonletter, so there's no need for a space. The recursive macro is now defined as a @. macro directly within the :normal. The blank lines and the numbers above 2 are now removed by a slick key sequence that cleans as it goes.

• Yo@0D@.: Both defines a macro in the ". register, and leaves a line full of junk. Both are useful. (This could also be S^V^R"D@., which puts the number and newline directly into "., or o^X^LjD@., which "copies" the number above it using line completion. Stroke counts are the same.)
• ^O@.: If you want an ^[ in a :normal, you have to prepend it with ^V so it inserts literally. ^O has no such restriction, and it gives us one command in normal mode, which is all we need. You'd think we'd drop back to insert mode after the macro was done, but insert mode escaping is automatic at the end of :normal.
• VEEkd: Deletes up to the next number we need. Does the right thing in several different contexts.
  1. Starting from 0, it deletes the lines with 0 and 1, leaving the cursor on 2.
  2. On every subsequent line :%normal hits, it deletes the line of junk created by the last @. definition, and all the blank lines that might come after. This works because E and e aren't like the rest of the word family movements—they skip blank lines.
  3. When running from the junk after the last prime, the second E will fail the macro, even though the cursor moved, and leave the editor in visual mode. When :normal runs the next (blank) line, ~ will block V from running, which would otherwise cancel visual mode. Since all the junk after the last prime ends up in a visual selection, you can delete it all in one stroke with d.

Though ~ fails on blank lines, at the end of this macro, it's running from visual mode. It should try to flip the case of the visual selection. The reason it doesn't is there's bug in Vim.

Vim devs: Don't fix this. I like my 35.

Alternate solutions

I showed an alternate 38 in my write-up of It's a factor. Here are some more.

541O1^[s@-+>>@.^[:%no<S-Tab>@-^A^Dp@.^M:g/^I/d^MZZ for 38.

This 38 by @KersonHsiao also implements the sieve of Eratosthenes, but in a different way. Instead of starting with all the numbers, he decided to start with a bunch of 1s. He adds them up to their final values as he goes in the :%normal. With that strategy, he can't clear the lines like I did; instead, he marks composite numbers by indenting their lines, and clearing the lines with tabs at the end.

C^I1^[qq^A>>Ypq540@q:g/\v^(^I^I+)\1+</d^M=(ZZ for 39.

Not the sieve of Eratosthenes this time. It starts by setting up the list of numbers, indented by tabs. If the number is 6, it will be indented by 6 tabs. Then a regex matches the tab sequences that can be split into 2 or more chunks of 2 or more tabs. The frowny removes the tabs at the end. There's a VimCast that does a great job describing this solution.

Let's cheat

If you use the factor program (included in GNU coreutils, and therefore available on lots of systems), you can save a couple strokes.

!!seq 541|factor^M:v/: \d*$/d^Mg&ZZ for 33.

This was mostly derived from work done by @federicogalassi. The seq program makes a list of numbers, and factor... factors them. Then you parse the output. The way :v and g& work together is especially elegant. The regex matches on lines that list only one factor, so :v can remove lines with more. g& uses that same regex to delete the factor listing itself on the remaining lines.

Read the manual

• :help range()
• :help registers: You should really know this.
• :help :normal: Less informative than I'd like. My article on tactical :normal may be more useful.
• :help ~: Just to prove the manual never says anything about how commands can fail macros. You just have to figure it out yourself. I like to run tests, such as @="~A". If the A command ran, ~ didn't fail in that position.
• :help j: Just to show it's listed together with ^J.
• :help :g
• :help i_CTRL-O
• :help e: Keep reading to the end of the section, and it talks about how e can skip blank lines.

Similar challenges

• It's a factor: Inspired by Prime Numbers. My write-up here
• Generate Fibonacci Numbers: Another famous number sequence.
• Append semicolon after expressions: Overcoming blank lines.