🔎

Linuxコマンドを駆使して素数リストを取得する

2022/02/21に公開

はじめに

はじめまして。初記事になります。nutmegと申します。
エンジニア歴は2年ほどですが、これまでアウトプットを怠ってきたので、自分がIT現場や自己学習で学んできた知識を発信してみようと思い、記事を書いています。
最近は現場でLinuxマシンを触ることが多いこと、2月にLPIC-1を取得したこともあり、知識の整理も兼ねています。誤記などございましたら、コメントいただけると幸いです。

Linuxコマンドは「手抜き」をするためにも便利です。テキストエディタ上でコマンドを整形する、文字列操作をするといった経験は、プログラマやSEの方であれば慣れ親しんでいる人も多いと思います。
中にはそれらの操作をLinuxコマンドを用いて実装する人もいると思います。

今回は、素数一覧を生成するコマンドを考えます。
「X以下の素数一覧が欲しい」みたいな状況のとき、主に以下の選択肢があると思います。

  • Webで検索して出てきたサイトから実際の値を取得、必要に応じてテキストエディタ等で整形する
  • 素数を生成するプログラムを書く(Pythonのsympyライブラリのis_prime()関数などのライブラリを使用する、試し割り法・エラトステネスの篩等を実装する、等)
  • 専用のツールを使用する
  • Linux上でコマンドを実行する
  • 少量なら自力で数え上げる

今回は、Linuxのコマンドを活用することで目的を達成しようという魂胆です。

注意点

  • ある程度Linuxコマンドについての知識があることを前提としています(需要があれば入門向けの記事も書いてみたいです)
  • この記事の方法がベストなやり方とは限りません
  • 実行環境によっては上手く動作しないかもしれません

筆者のLinux環境はRochy Linux 8です。
Debian系でも基本的な動作は変わらないと思いますが、BSD系のMac OS等ではgrep/sed/find/awk等諸々のコマンドの実装が異なるので注意してください。
Linuxコマンドの範囲が不明瞭かもしれませんが、標準的に含まれるようなツールなどを含む場合があります。

各ツールの環境について

以下の環境で動作を確認しています。RHEL、Ubuntu等では問題なく動作すると思いますが、もし気づいた点があれば教えていただけると幸いです。

  • bash / GNU bash, version 4.4.20(1)-release (x86_64-redhat-linux-gnu)
  • openssl / OpenSSL 1.1.1k FIPS 25 Mar 2021
  • awk / GNU Awk 4.2.1, API: 2.0 (GNU MPFR 3.1.6-p2, GNU MP 6.1.2)
  • sed / sed (GNU sed) 4.5

実行コマンドと出力結果

先に全体のコマンドとその実行結果を記載します。

実行コマンド(全体像)

openssl prime {2..100} | awk -F'[()]' '!/not/{print $2}' | sed -z 's/\n/, /g;s/, $/]/;s/^/prime = [/'

出力結果

prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

コマンドを|で区切って、1つずつ順番に見ていきます。

1. 素数判定

素数判定そのものにはopensslのprimeというコマンドを使います。

openssl primeコマンドによる単一の値の素数判定

openssl prime 57

出力結果

39 (57) is not prime

入力をNとした場合の出力結果は、

{Nの16進数表記} ({Nの10進数表記}) is not prime

と表示されます。
素数の場合は「not prime」の部分が「prime」と表示されます。
複数の数値をまとめて指定できるので、2から100までの範囲の場合は以下のように指定します。

Bashのブレース展開機能

openssl prime {2..100}

この表記は以下と同値です。Bashのブレース展開[1]という機能によって、実行時に以下のコマンドに解釈されます。

openssl prime 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

1実行時点での出力

2 (2) is prime
3 (3) is prime
4 (4) is not prime
5 (5) is prime
・・・(途中略)
60 (96) is not prime
61 (97) is prime
62 (98) is not prime
63 (99) is not prime
64 (100) is not prime```

()の中に目的の数字があります。
2ではこれを取り出してみましょう。
先頭の数字を取り出して16→10の基数変換をするのも1つの手だと思います。

2. awkで「not」が含む行を除外しつつ()内の文字を抽出

出力結果のうち、notが含まれている行は素数ではない[2]ことを意味しています。

awkは多彩なことが出来るので、別で記事を書きたいと思いますが、ここでは最低限の説明をします。

特定行の除外

特定の行を表示する場合、awkでは

awk '/pattern/'

と指定します。この場合はpatternを含んだ行全体を出力し、以下と同値となります。

awk '/pattern/{print $0}'

除外する場合は、『/pattern/』の前に『!』を追加します。
grepの-vオプション[3]と同じ働きをします。

区切り文字を指定(-Fオプション)

awkはデフォルトでは半角スペースで行を分解し、$1, $2, …と変数に格納していきます。
この区切り文字を変更するために使うのが-Fオプションです。
cutコマンドでも-dオプションによって区切り文字を変えることが出来ますが、awkの場合は正規表現を使用して複数の文字を指定することが可能です。
正規表現で[abc]と記載すると、中の文字どれか1字にマッチします。今回は( )[4]で区切っています。

62 (98) is not prime

↓awkの$1~$3に以下のように格納される

$1 ... 62 
$2 ... 98
$3 ... is not prime

(,)で区切ったあと「not」を含まない行の$2を出力する

$2が欲しい値ですので、notを含まない行について、print $2と記述します。
これらを踏まえて、1,2を合わせると以下のようなコマンドとなります。

openssl prime {2..100} | awk -F'[()]' '!/not/{print $2}'

上記コマンドを実行時点での出力結果は、以下のようになります。

2
3
5
・・・(途中略)
83
89
97

ここまでで素数一覧は抽出出来ているので、場合によってはここで操作を中止しても良いです。

3. sedで整形してリスト形式に変換する

素数リストをそのままプログラムのコードのなかで使用する場合などを想定して、リスト形式に直しておきましょう。
以下のようなPython向けのコードに変形します。

prime = [2, 3, ... , 97]

仕上げのsedコマンド

openssl prime {2..100} | awk -F'[()]' '!/not/{print $2}' | sed -z 's/\n/, /g;s/, $/]/;s/^/prime = [/'

sedで改行コード\nを使用するために「-z」オプションを付けます。
sedでは、「;」を区切りとして、以下の置換コマンドを順番に実行しています。

コマンド 説明
s/\n/, /g 改行コードを『, 』に変換
s/, $/]/ 末尾の『, 』を削除して『]』を付け足す
s/^/prime = [/ 先頭に『prime = [』を付け足す

あとは出力結果をコピーして、Python等のソースに貼り付ければ良いと。

まとめ

有限個の文字列や数値のリストが欲しい場合は、この要領でLinux上で処理をすると楽なケースが多いかなと思っています。
最後の3は言語(や使用目的)に合わせて工夫が必要ですが、何をするにもsed/awkがとても便利であることが伝われば良いなと思いました。

ここまで読んでくださってありがとうございました。

脚注
  1. この機能もかなり強力です!別の機会に紹介します。 ↩︎

  2. ※2以上の素数ではない整数は他の素数の積によって表せ、「合成数」と呼びます。 ↩︎

  3. grep -v 'pattern' が、 awk '!/pattern/' と同じ働きになります。ただし、使用できる正規表現に細かい違いがあります。 ↩︎

  4. 拡張正規表現では'()'が特殊な意味を持ってしまうので\(, \)と表現する場合もありますが、正規表現の[]内では一部の特殊文字を除き、エスケープ(※特殊文字直前にバックスラッシュ'\'を付けて特殊な意味を打ち消すこと)が不要となります。(例:「.」など) ↩︎

GitHubで編集を提案

Discussion