CodeIQ「スーパー素数」問題に参加しました。

CodeIQ「スーパー素数」問題の公開期間が終了したということで、自分の答案を公開したいと思います。

利用した言語はBash――なのですが、実際はawkですね(´・ω・｀) プログラミング・パズルをBashで解こうとすると、どうしてもawkを多用しがちです。

#!/bin/bash

awk '{
    n = 200000

    eratosthenes[0] = eratosthenes[1] = 1
    for (i = 2; i <= sqrt(n); i++) {
        if (eratosthenes[i] == 1) continue;
        for (j = i * 2; j <= n; j += i) eratosthenes[j] = 1;
    }

    for (i = 1; i <= n; i++) {
        if (eratosthenes[i] != 1) primes[++x] = i;
    }

    for(i = 1; i <= 2017; i++) super_primes[i] = primes[primes[i]];

    print(super_primes[$0])
}'

問題の内容としては「素数列の素数番目だけを集めた『スーパー素数』列のn番目を求めなさい」というもの。解答にあたっては素数列を求める必要があるのですが、問題の制約上200000程度まで計算せねばなりません。よって比較的効率のよいアルゴリズム、すなわち「エラトステネスのふるい」により素数列挙を行いました。実際にやってみたわけではないのですが、試し割りのような計算量の多いアルゴリズムだと、CodeIQの制限時間(1秒)には間に合わないと思います。

要するに本問はエラトステネスのふるいがきちんと実装できるかということが問われていたのでした。

おまけ: 現役システムエンジニアらしく、VBAでも実装しておきました(´・ω・｀)

Sub SuperPrimes()
    Const UpperBound As Long = 200000
    Const SuperPrimesUpperBound As Long = 2017

    Dim X As Long

    ' エラトステネスのふるい: 素数判定を行う。
    Dim IsPrime(UpperBound + 1) As Boolean
    For X = 0 To UpperBound
        IsPrime(X) = True
    Next X
    IsPrime(0) = IsPrime(1) = False

    For X = 2 To Sqr(UpperBound)
        If IsPrime(X) Then
            Dim NonPrime As Long
            For NonPrime = X * 2 To UpperBound Step X
                IsPrime(NonPrime) = False
            Next NonPrime
        End If
    Next X

    ' 素数列を求める。
    Dim Primes(UpperBound) As Long
    Dim PrimesIdx As Long
    PrimesIdx = 1
    For X = 2 To UpperBound
        If IsPrime(X) Then
            Primes(PrimesIdx) = X
            PrimesIdx = PrimesIdx + 1
        End If
    Next X

    ' スーパー素数列を求める。
    Dim SuperPrimes(SuperPrimesUpperBound) As Long
    For X = 1 To SuperPrimesUpperBound
        SuperPrimes(X) = Primes(Primes(X))
    Next X

    ' スーパー素数列をシートに書き出す。
    For X = 1 To SuperPrimesUpperBound
        Cells(X, 1).Value = SuperPrimes(X)
    Next X
End Sub

以上のマクロをエクセルに張り付けて実行すると、シートのA列にスーパー素数が書き出されます。業務で「素数」「エラトステネスのふるい」「スーパー素数」が必要になりそうな方は参考にしてください(｀・ω・´)ｼｬｷｰﾝ