5
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Last updated at Posted at 2016-01-12

概要

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

しかし、シェル芸2による解答は、私が探した限りでは、殆ど見つからなかった。
そこで、私自身の勉強も兼ねて、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$万以下の全ての素数の和を求めよ.

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

解法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/'にした。
  • 先に解答されちゃった><
- ...ので、対抗してこちらも今日のうちにProblem 10も投稿することにするw - 1日1問のつもりなので、明日はお休みするかも?
  1. About - Project Euler (https://projecteuler.net)

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

  3. 142913828922

5
5
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
5
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?