完美的力量检查

Question

完美的幂是N,其中A ^ B = N(A> = 1,B> = 2)

这是我的代码.我试图找出1和我选择的上限之间存在多少这些数字.

    static void Main(string[] args)
    {
        int PPwr_Count = 1; //number 1 is included by default.
        int Top_Limit = 1000000; //Can be any number up to 10^9
        for (int Number = 2; Number <= Top_Limit; Number++)
        {
            int myLog = (int)Math.Floor(Math.Log(Number, 2) + 1);
            for (int i = 2; i <= myLog; i++) 
            {
                //As a Math rule I only need to check below Base 2 Log of number
                int x = Convert.ToInt32(Math.Pow(Number, 1.0 / i));
                 if (Number == Math.Pow(x, i))
                 {
                     PPwr_Count++;
                     break;
                 }
                 else continue;
            }
        }
     } 

它目前正在运作.可悲的是,在大约1,000,000次检查后,它变得非常缓慢.无论如何要提高这个算法的速度？

Answer 1

Math.Log很贵,Math.Pow很贵,双打很贵.你知道什么不贵吗？乘以整数.

一些理论加工:如果A ^ B == n且n <10 ^ 9且B> = 2,则最大A接近5*10 ^ 4.所以让我们拥有一套完美的力量.当i*i <= max_n时迭代2,如果我没有设置,则添加i*i,i*i*i,依此类推,而不是max_n.如果A = C ^ D,则A ^ B = C ^(B*D),并且已经设置.

static void Main(string[] args)
    {
        int PPwr_Count = 1; //number 1 is included by default.
        int Top_Limit = 1000000000; //Can be any number up to 10^9
        HashSet<int> hs = new HashSet<int>();

        for (int A = 2; A * A <= Top_Limit; ++A)
        {
            if (!hs.Contains(A))
            {
                //We use long because of possible overflow
                long t = A*A;
                while (t <= Top_Limit)
                {
                    hs.Add((int)t);
                    t *= A;
                    PPwr_Count++;
                }
            }
        }
        Console.WriteLine(PPwr_Count);
    }

编辑:这在我的笔记本电脑上的调试运行不到半秒.