Problem187 半素数

問題

合成数とは2つ以上の素因数を含む整数のことである.
例えば15 = 3 × 5, 9 = 3 × 3, 12 = 2 × 2 × 3が合成数である.

30以下には丁度2つの素因数を含む合成数 (異なる素因数でなくてもよい) が, 10個存在する.
4, 6, 9, 10, 14, 15, 21, 22, 25, 26がそうである.

合成数 n < 10の8乗について,
丁度2つの素因数を含む合成数 (異なる素因数でなくてもよい) はいくつあるか.

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int Jyougen = 100000000;

    static int[] SosuuArr;

    //エラトステネスの篩
    static void Eratosthenes()
    {
        var IsSosuuArr = new System.Collections.BitArray(Jyougen + 1);

        for (int I = 2; I <= IsSosuuArr.Count - 1; I++) {
            IsSosuuArr[I] = true;
        }
        for (int I = 2; I * I <= IsSosuuArr.Count - 1; I++) {
            if (I != 2 && I % 2 == 0) continue;

            if (IsSosuuArr[I]) {
                for (int J = I * 2; J <= IsSosuuArr.Count - 1; J += I) {
                    IsSosuuArr[J] = false;
                }
            }
        }
        var SosuuList = new List<int>();
        for (int I = 2; I <= IsSosuuArr.Count - 1; I++)
            if (IsSosuuArr[I]) SosuuList.Add(I);

        SosuuArr = SosuuList.ToArray();
    }

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        Eratosthenes();

        int UB = SosuuArr.GetUpperBound(0);

        int AnswerCnt = 0;
        for (int I = 0; I <= UB; I++) {
            //解が存在しない場合
            if ((long)SosuuArr[I] * SosuuArr[I] >= Jyougen)
                break;

            int MaxInd = ExecNibunHou(I, UB);
            int CurrCnt = MaxInd - I + 1;
            AnswerCnt += CurrCnt;
        }
        Console.WriteLine("解は{0}。経過時間={1}", AnswerCnt, sw.Elapsed);
    }

    //2分法で、積が10の8乗未満の、最大の添字を返す
    static int ExecNibunHou(int pL, int pR)
    {
        int L = pL;
        int R = pR;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            //Console.WriteLine("L={0},R={1},Mid={2}。{3}*{4}={5}",
            //    L, R, Mid,
            //    SosuuArr[pL], SosuuArr[Mid], (long)SosuuArr[pL] * SosuuArr[Mid]);

            bool IsOver = ((long)SosuuArr[pL] * SosuuArr[Mid] >= Jyougen);
            if (IsOver) R = Mid;
            else L = Mid;
        }
        return L;
    }
}

実行結果

解は17427258。経過時間=00:00:05.6386783

解説

素数ごとに、掛けて10の8乗未満となる素数の個数を
2分法で求めてます。