【C++】N以下の数と素数の個数との差がK以上となる数の個数を求めるアルゴリズム

2つの整数 N と K が与えられます。目的は、以下の条件を両方とも満たす数の個数を求めることです。

• その数が N 以下であること

• |その数 − 素数の個数| ≥ K であること（ここで「素数の個数」とは、その数以下に存在する素数の総数を指します）

具体例

入力

N = 5, K = 2

出力

N以下の数のうち、それまでの素数の個数との差がK以上となる数は: 2個

説明

条件を満たす数は次の2つです:
5（5−2≥2）と 4（4−2≥2）

入力

N = 10, K = 6

出力

N以下の数のうち、それまでの素数の個数との差がK以上となる数は: 1個

説明

条件を満たす数は次の1つです:
10（10−4≥6）

本プログラムのアプローチ

この解法では、計算量を削減するために二分探索を利用します。数 num 以下の素数の個数を count1、num+1 以下の素数の個数を count2 とすると、(num+1) − count2 ≥ num − count1 という関係が常に成り立ちます。これは、数が1増えても素数の個数は高々1しか増えないためです。したがって、ある数 num が条件を満たすならば、num+1 以降も必ず条件を満たします。二分探索で条件を満たす最小の数 num を1つ見つければ、num から N までのすべての数が条件を満たすことになり、その個数は「N − num + 1」で一気に求められます。

• N と K を入力として受け取ります。

• 配列 arr[] は、インデックス i に「i 以下の素数の個数」を格納するために使用します。

• 関数 set_prime() が、配列 arr[] に素数の累積個数を書き込みます。

• 配列 check[i] は、i が素数であれば true、そうでなければ false を格納します。

• 0 と 1 は素数ではないため、check[0] = check[1] = false と設定します。

• i = 2 から i * i < size（1000001）の範囲で check を走査し、check[i] が 1（素数）の場合は、j = i * 2 から j < size まで j を i ずつ増やしながら check[j] をすべて 0 に設定します（いわゆるエラトステネスの篩）。

• 続いて for ループで arr[] を走査・更新します。まず arr[i] = arr[i − 1] とし、i 自身が素数であれば arr[i]++ として個数を1増やします。

• 関数 total(int N, int K) は N と K を受け取り、「N以下の数のうち、それまでの素数の個数との差がK以上となる数」の個数を返します。

• set_prime() を呼び出します。

• temp_1 = 1、temp_2 = N と初期化し、count の初期値は 0 とします。

• while ループによる二分探索では、set = (temp_1 + temp_2) >> 1（探索区間の中央値）を取ります。

• set − arr[set] ≥ K であれば条件を満たしているので、count を set で更新し、temp_2 = set − 1 としてより小さい側を探索します。

• そうでなければ temp_1 = set + 1 として大きい側を探索します。

• ループ終了後、count には条件を満たす最小の数が入っています。最終的な答えは、該当する数が存在すれば N − count + 1、存在しなければ 0 となります。

• すべての処理が完了したら、count を結果として返します。

例

#include <bits/stdc++.h>
using namespace std;
#define size 1000001
int arr[size];
void set_prime(){
    bool check[size];
    memset(check, 1, sizeof(check));
    check[0] = 0;
    check[1] = 0;
    for (int i = 2; i * i < size; i++){
        if(check[i] == 1){
            for (int j = i * 2; j < size; j += i){
                check[j] = 0;
            }
        }
    }
    for (int i = 1; i < size; i++){
        arr[i] = arr[i - 1];
        if(check[i] == 1){
            arr[i]++;
        }
    }
}
int total(int N, int K){
    set_prime();
    int temp_1 = 1;
    int temp_2 = N;
    int count = 0;
    while (temp_1 <= temp_2){
        int set = (temp_1 + temp_2) >> 1;
        if (set - arr[set] >= K){
            count = set;
            temp_2 = set - 1;
        } else {
            temp_1 = set + 1;
        }
    }
    count = (count ? N - count + 1 : 0);
    return count;
}
int main(){
    int N = 12, K = 5;
    cout<<"N以下の数のうち、それまでの素数の個数との差がK以上となる数の個数は: "<<total(N, K);
    return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます。

N以下の数のうち、それまでの素数の個数との差がK以上となる数の個数は: 4