Project Euler : Problem 29 『Distinct powers』

犬と猫 / kagawa_ymg

問題

　a^b (2 ≤ a ≤ 100, 2 ≤ b ≤ 100) で作れる数は何個あるか？

値が大きいので極力計算しない方向で

　100¹⁰⁰なんか計算してられないし。
何より、100¹⁰⁰までの数字をチェックしないといけないなんて悪夢だ…。

重複を見る

　例えば、2⁴ と 4² は共に16で重複してる。
なぜ重複してるのかというと、4 = 2²なので、
4²
= (2²)²
= 2^2×2
= 2⁴
　同じ底aで揃えた場合、同じ指数bになれば同じ数字だとわかる。
この場合、底と指数が違うのに計算結果が同じになるので、値のダブルチェックを回避する。

　……とりあえず説明が凄くめんどくさいので、後はコードを見てください(手抜き)

コード

using System.Diagnostics;
using System.Linq;

namespace Problem29
{
    class Program
    {
        //範囲
        static int min = 2;
        static int max = 100;

        static void Main(string[] args)
        {
            Debug.WriteLine(DistinctPowers());
        }

        static int DistinctPowers()
        {
            bool[] findA = new bool[max + 1];
            int sum = 0;

            for (int a = min; a <= max; a++)
            {
                if (findA[a] == false)
                {
                    int b = maxB(a, findA);

                    sum += NumberCount(b);
                }
            }

            return sum;
        }

        /// <summary>
        /// a^bの最も大きいbを調べる
        /// </summary>
        static int maxB(int a, bool[] findA)
        {
            int b = 0;

            for (int i = a; i <= max; i *= a)
            {
                findA[i] = true;
                b++;
            }

            return b;
        }

        /// <summary>
        /// b乗まである場合の出現個数を求める
        /// </summary>
        static int NumberCount(int b)
        {
            if (b == 1) return max - min + 1;

            bool[] findB = new bool[b * max + 1];

            for (int d = 1; d <= b; d++)
            {
                for (int j = min * d; j <= d * max; j += d)
                {
                    if (findB[j] == false) findB[j] = true;
                }
            }

            return findB.Where(obj => obj == true).Count();
        }
    }
}