C++の素数ポイントとは？数値を2つの素数に分割するインデックスの求め方

この問題では、ある数値 N が与えられます。私たちのタスクは、その数値が持つすべての素数ポイントを出力することです。素数ポイントがひとつも存在しない場合は、-1 を出力します。

素数ポイントとは？

素数ポイント（Prime Points）とは、数値を左右の2つの部分に分割したときに、その両方の部分が素数となる分割位置（インデックス）のことです。

具体例を使って問題を理解しましょう。

入力: 2359
出力: 1

説明: インデックス 1 の位置で数値を分割すると、「2」と「59」という2つの素数が得られます。したがって、1 が素数ポイントとなります。

解法のアプローチ

この問題を解くための手順は以下の通りです。

1. 数値を左右に分割できるすべての位置を列挙します。
2. 各分割位置について、左側と右側の数値を取り出します。
3. 取り出した2つの数値がどちらも素数かどうかを判定します。
4. 両方が素数であれば、そのインデックスを出力します。
5. 有効な分割位置がひとつも見つからなければ、-1 を出力します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

// 桁数を数える関数
int countDigits(int n) {
    int count = 0;
    while (n > 0){
        count++;
        n = n/10;
    }
    return count;
}

// 素数判定を行う関数（6k±1 最適化を使用）
int checkPrime(int n) {
    if (n <= 1)
        return -1;
    if (n <= 3)
        return 0;
    if (n%2 == 0 || n%3 == 0)
        return -1;
    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
            return -1;
    return 0;
}

// 素数ポイントを検出して出力する関数
void primePoints(int n) {
    int count = countDigits(n);
    if (count==1 || count==2){
        cout << "-1";
        return;
    }
    bool found = false;
    for (int i=1; i<(count-1); i++){
        int left = n / ((int)pow(10,count-i));
        int right = n % ((int)pow(10,count-i-1));
        if (checkPrime(left) == 0 && checkPrime(right) == 0){
            cout<<i<<"\t";
            found = true;
        }
    }
    if (found == false)
    cout << "-1";
}

int main() {
    int N = 2359;
    cout<<"数値 "<<N<<" のすべての素数ポイント:\n";
    primePoints(N);
    return 0;
}

出力結果

数値 2359 のすべての素数ポイント:
1

コードの解説

countDigits 関数

数値を 10 で割り続けることで桁数をカウントします。分割位置を列挙するために必要となる関数です。

checkPrime 関数

素数判定を効率的に行うため、6k±1 の最適化を使用しています。すべての素数は 6k±1 の形で表せるという性質を利用し、√n まで 6 ずつ増やしながら判定することで、計算量を O(√n) に抑えています。

primePoints 関数

各分割位置 i について、pow 関数を使って左側の数値（n を 10^(桁数-i) で割った商）と右側の数値（n を 10^(桁数-i-1) で割った余り）を求めます。両方が素数であればインデックスを出力し、最後まで有効な分割が見つからなければ -1 を出力します。

計算量

桁数を d、数値の大きさを N とすると、分割位置の列挙に O(d)、各位置での素数判定に O(√N) かかるため、全体の時間計算量は O(d × √N) となります。