Project Eulerをシェル芸で解いてみる(Problem 10)

概要

Project Euler¹は、数学的な問題解決能力を要求する、プログラミング問題集・オンラインプログラミングジャッジである。
一般的なオンラインプログラミングジャッジとは異なり、解答するプログラミング言語は、特に限定されていない。
フォームに入力した値だけで正誤を判別するため、適切なアルゴリズムさえ考案できれば、あらゆるプログラミング言語で解答することが可能である。
そのため、Web上では様々な手法による解答が公開されている。

しかし、シェル芸²による解答は、私が探した限りでは、殆ど見つからなかった。
そこで、私自身の勉強も兼ねて、Project Eulerをシェル芸で解いてみることにした。

本記事では、Project EulerのProblem 10を、シェル芸で解いた際の過程を述べる。

実行環境

• Arch Linux (x86_64, 4.3.3-2-ARCH)
• bash (4.3.42, POSIX互換モード)
• GNU coreutils (8.24)

• gawk (4.1.3)

• bsd-games (2.17)

問題文

[原文 (https://projecteuler.net/problem=10)]

The sum of the primes below $10$ is $2 + 3 + 5 + 7 = 17$.
Find the sum of all the primes below two million.

[日本語訳 (http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2010)]

$10$ 以下の素数の和は $2 + 3 + 5 + 7 = 17$ である.
$200$万以下の全ての素数の和を求めよ.

正答は、注釈³に記載する。

解法1

prob_010.sh

1   #!/bin/sh
2   
3   seq 1 2000000 \
4   | # 入力の生成
5   factor \
6   | # 素因数分解
7   awk 'NF == 2 {print $2}' \
8   | # 素数の抽出
9   tr '\n' '+' \
10  | # 数式の生成_1
11  sed -e 's/\+$/\n/' \
12  | # 数式の生成_2
13  bc
14    # 計算結果の出力

解説1

この解法による処理の詳細は、コードに記載してあるコメントの通りである。

また、bsd-gamesに含まれるprimesを用いたより短い解き方を、解法2として述べる。

解法2

prob_010_2.sh

1   #!/bin/sh
2   
3   primes 2 2000000 \
4   | # 2000000以下の素数の列挙
5   awk '{sum+=$0} END {print sum}'
6     # 和の出力

解説2

この解法による処理の詳細は、コードに記載してあるコメントの通りである。

雑記

• 「こんな別解があるよ」や、「こうすればもっと効率化できるぜ」、「こう書けばエレガントですわよ」等の意見がありましたら、気軽に教えていただけますと幸いです🐺

• 現在の進捗状況 -> https://github.com/gin135/Project_Euler/tree/master/sh
  
  

• 今回の問題も手抜き解説。

  • いやでも、今回はこれ以上説明のしようが無いと思うので...

• 数式の生成に関しては、tr '\n' '+' | sed -e 's/\+$/\n/'とするよりも、xargs | tr ' ' '+'としたほうがエレガントではある。

  • trで改行コードを演算子に変換する方法だと、末尾に余分な演算子がくっついてしまうので。
  • けれど、xargs(正確にはOS)には、一度に扱える引数の総バイト数に上限がある >> $ getconf ARG_MAX
  • 今回の問題はその上限に引っかかってしまい、数式がうまく生成できないため、tr '\n' '+' | sed -e 's/\+$/\n/'にした。

• 先に解答されちゃった＞＜
  

  yes | sed -n = | factor | awk '$0=$2*!$3' | awk '$0>=2000000{exit}{s+=$0}END{print s}' Problem 10. sed -n =といういい話を聞いたので使ってみた #シェル芸

  — 卒論まで21日のMasaki Waga (@MasWag) January 12, 2016

  • ...ので、対抗してこちらも今日のうちにProblem 10も投稿することにするw
  • 1日1問のつもりなので、明日はお休みするかも？

---

---

1. About - Project Euler (https://projecteuler.net) ↩

2. シェル芸の定義 >> シェル芸 - 上田ブログ (https://blog.ueda.asia/?page_id=1434) ↩

3. 142913828922 ↩