素数とエマープ

エマープ…ある素数をひっくり返してもやはり素数、つまり (13, 31), (17, 71) のような組み合わせ。

綴りはemirp、素数primeのリバースです。

結果を先に

N = 999
素数の個数: 168
= エマープ素数 =
[(13, 31), (17, 71), (37, 73), (79, 97), (107, 701), (113, 311), (149, 941), (157, 751), (167, 761), (179, 971), (199, 991), (337, 733), (347, 743), (359, 953), (389, 983), (709, 907), (739, 937), (769, 967)]
= 回文素数 =
[(11, 11), (101, 101), (131, 131), (151, 151), (181, 181), (191, 191), (313, 313), (353, 353), (373, 373), (383, 383), (727, 727), (757, 757), (787, 787), (797, 797), (919, 919), (929, 929)]
0.005120 秒

今回の全体コード

GitHub Prime-Emirp

なにはともあれ、まずは素数

応用情報技術者試験のプログラミング問題に素数を求めるアルゴリズムがあったのを思い出したので、素数を求めるついでにエマープも出力してみようかと思いました。

参考にしたのは応用情報の令和6年秋 午後問題3からになります。

素数を求める

試験問題の仕様ではちょっと私の力ではバグが出そうだったので、ちょっぴり書き換えました。

def prime_number(N: int):
    numbers = [2]  # 結果となる素数の一覧を格納する一次元配列
    is_prime = []
    # counter = 0

    start_number = 3
    c = start_number
    while c <= N:
        numbers.append(c)
        c += 2
    is_prime = [True] * len(numbers)# 仮のTrue. 初期状態は"仮に"すべて素数とする
    
    d = 1  # 3 から調査していく(2が配列0番目なので)
    while d < len(is_prime):
        # 既に素数でないと判定されている場合はスキップ
        if is_prime[d] == False:
            d += 1
            continue

        # 素数でないのを判定していく
        search_number = numbers[d] * 2
        while search_number <= N:
            try:
                _index = numbers.index(search_number)
            except ValueError:
                # リストに値がない場合
                # print(f'無し {search_number}')
                pass
            else:
                if is_prime[_index]:
                    is_prime[_index] = False
                    # print(f'{search_number} is not found in primes')
                    # counter += 1
            finally:
                search_number += numbers[d]
                continue
        d += 1

    # 素数をピックアップ
    primes = [numbers[i] for i in range(len(is_prime)) if is_prime[i]]
    # Numpyにmaskという機能があるらしい

    # print(f'計算回数: {counter}')
    return primes

エマープ (+ 回分素数)

取得した素数のリストから、1つずつ処理していきます。

• 数値をひっくり返す
• その数値がリストの中に含まれているか確認

[注意1] 素数を求めたい上限の値を99や999など、桁が増える1つ手前までの数値を指定しなければなりません。
[注意2] 回分素数と言うのもあるということで、ついでに出力できます

def emirp_number(primes: list, type: str = "emirp"):
    # 数値をひっくり返して、その数も素数であることを確認する
    emirps = []

    i = 0
    while i < len(primes):
        n = primes[i]

        # 1桁の数はスキップ
        if len(str(n)) <= 1:
            i += 1
            continue

        # 数値をひっくり返す
        reversed_n = int(str(n)[::-1])
        # リストより検索
        try:
            _index = primes.index(reversed_n)
        except ValueError:
            # リストに値がない場合
            pass
        else:
            if type == "emirp":
                if n < reversed_n:  # "回文素数は除く
                    emirps.append((n, reversed_n))
            elif type == "palindromic_prime":
                if n == reversed_n:
                    # "回文素数も"含まれる
                    emirps.append((n, reversed_n))
            else:
                if n <= reversed_n:  # イコールを付けると"回文素数も"含まれる
                    emirps.append((n, reversed_n))
        i += 1

    return emirps

今後の課題として修正を考えたいところ

数桁ほどのエマープを求めるのは良いのですが、もし桁数を増やした場合、速度はだんだん遅くなるのでこの辺を改善していけたら。

以上になります。またお会いしましょう