【C++】範囲内の「素因数が2と3のみ」の数を数える方法

2つの整数 START と END が与えられ、この2つで数値の範囲を定義します。この記事のゴールは、範囲 [START, END] 内に存在する「素因数が2と3だけ」の数、すなわち 2^a × 3^b（a, b は 0 以上の整数）の形で表せる数を見つけ出し、その個数を求めることです。

調べ方はシンプルです。START から END まで順に各数値を走査し、それぞれの数が2と3だけで割り切れるかを確認します。割り切れる場合は実際に割って数を小さくしていき、どちらでも割れなくなった時点でループを抜けます。最終的にその数が1にまで約分されていれば、素因数は2と3のみであると判定できます。

それでは、具体例で確認しましょう。

入力例 1

START=20 END=25

出力例 1

素因数が2と3のみの数: 1

説明

各数の素因数分解:
20 = 2×2×5
21 = 3×7
22 = 2×11
23 = 23（素数）
24 = 2×2×2×3
25 = 5×5
素因数が2と3だけなのは 24 のみです。

入力例 2

START=1000 END=1500

出力例 2

素因数が2と3のみの数: 4

説明

1024、1152、1296、1458 の4つが該当する数です。

プログラムで使用するアプローチ

• 範囲を表す整数 START と END を入力として受け取ります。
• 関数 twothreeFactors(int start, int end) が範囲を受け取り、素因数が2と3のみの数の個数を返します。
• カウント用変数 count を 0 で初期化します。
• for ループで i = start から i = end まで、範囲内の数を順に走査します。
• 各数値 num = i に対して、while ループ内で num % 2 == 0 であれば 2 で割ります。
• 続いて num % 3 == 0 であれば 3 で割ります。どちらでも割り切れない場合は break で while ループを抜けます。
• while ループ終了後も num が 1 になっていれば count をインクリメントします。
• すべてのループが完了した時点で、count には素因数が2と3のみの数の総数が格納されています。
• count を結果として返します。

計算量を考えてみましょう。範囲内の各数値に対して行う除算は、数を2以上の倍率で縮小していくため高々 log₂N 回程度であり、全体の計算量は O((END − START + 1) × log N) となります。非常に効率的なアプローチです。

C++ 実装例

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

int twothreeFactors(int start, int end){
    // 1 が誤ってカウントされないよう、start が 1 なら 2 から開始する
    if (start == 1)
        { start++; }
    int count = 0;
    for (int i = start; i <= end; i++) {
        int num = i;
        while(num>1){
            // 2 で割り切れる場合は 2 で割る
            if(num % 2 == 0)
                { num /= 2; }
            // 3 で割り切れる場合は 3 で割る
            else if (num % 3 == 0)
                { num /= 3; }
            else // 2 でも 3 でも割り切れない場合はループを抜ける
                { break; }
        }
        // 1 に約分されていれば、素因数は 2 と 3 のみということ
        if (num == 1)
            { count++; }
    }
    return count;
}

int main(){
    int START = 10, END = 20;
    cout << "素因数が2と3のみの数:" << twothreeFactors(START, END);
    return 0;
}

実行結果

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

素因数が2と3のみの数:3

START=10、END=20 の場合、12（= 2×2×3）、16（= 2×2×2×2）、18（= 2×3×3）の3つが条件を満たすため、結果は 3 となります。