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

概要

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

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

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

実行環境

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

問題文

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

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?

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

素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
10 001 番目の素数を求めよ.

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

解法

prob_007.sh

1	#!/bin/sh
2	
3	yes 高須クリニック \
4	| # 入力行を無限に出力
5	awk '$0=NR' \
6	| # 入力行を行番号に対応した自然数へ変換
7	factor \
8	| # 自然数を素因数分解
9	awk 'NF == 2 {print $2}' \
10	| # 素数の抽出
11	awk 'NR == 10001 {print; exit}'
12	  # 10001番目の素数の出力

解法の解説

素数を小さい方から順に列挙し、10001番目になるものを抽出すれば良い。

この解法による処理の詳細は、概ねコードに記載してあるコメントの通りである。
以下、概略のみを述べる。

まず、3~9行目のコマンドによって、素数を列挙する。
そして、11行目のawkによって、10001番目の素数を抽出している。

以上が、10001番目の素数を求める方法である。

参考にしたもの

# yes '高須クリニック' #危険シェル芸

— ぐれさん (@grethlen) 2014, 8月 20

シェル芸界に危険人物が多いと言われるのは、だいたいこの人のせい。

雑記

• 「こんな別解があるよ」や、「こうすればもっと効率化できるぜ」、「こう書けばエレガントですわよ」等の意見がありましたら、気軽に教えていただけますと幸いです🐺
• 現在の進捗状況 -> https://github.com/gin135/Project_Euler/tree/master/sh

• AWKは至高のスクリプト言語(当社比)。
• しばらくは(シェル芸的に)簡単な問題が連続しているので、当面は手抜き解説が続くかもしれません。

---

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

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

3. 104743 ↩