完美电源检查

本文关键字：检查 电源 完美 | 更新日期: 2023-09-27 18:20:29

完美幂是一个数字 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 次检查后，它变得非常慢。无论如何，如何提高此算法的速度？

完美电源检查

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

一些理论：如果 A^B == n 和 n<10^9 和 B>=2 比最大 A 接近 5*10^4。因此，让我们拥有一套完美的力量。从 2 迭代，而 i*i<=max_n，如果 i 不在集合中，则添加 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);
    }

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

将Math.Log(Number, 2) + 1移出 for 循环。

int myLog = (int)Math.Floor(Math.Log(Number, 2) + 1);
for (int i = 2; i <= myLog; i++)
在

A 和 B 的空间中搜索比在 N 的空间中搜索更容易。A 来自 [2,...,sqrt(N(]，B 来自 [素数列表]。

我倾向于使用完全不同的方法。

首先，创建一个迭代器，枚举所有素数，直到最大大小的平方根。所以 2， 3， 5， 7， 11...

更新：没有等待不起作用。例如，这并不能将 36 作为完美的幂。

让我修改一下。

创建一个迭代器，枚举从 2 到最大大小的平方根的所有数字。

接下来，创建一个迭代器，枚举特定给定数字的所有完美幂，直至最大大小。那是 22， 23， 24， ...

现在，将两个迭代器与多选查询相结合，以便生成：2 2、23、24、...32， 3 3， 3 4， ...， 42， 43， 44， ...

从结果查询中构建一个哈希集，以形成所有小于所有数字的最大大小到最大大小的平方根的所有完美幂的并集。

生成的哈希集的大小是您查找的数字。

另一种选择是，与其遍历所有数字并检查它们是否是一种力量，不如做相反的事情：产生所有完美的力量。

所以如果你从基数 2 开始，计算2^1、2^2等。然后计算3^1、3^2、3^3等。您可能还希望将每个结果存储在HashSet中，以便消除双精度。最后，计数就像hash.Count一样简单

我不确定它的性能如何与您的代码相提并论(它肯定空间效率较低(，但这是另一个角度可能会起作用。

我会尝试从另一个方向使用算法。

从 a = 2 和 b = 2 开始，遍历每个 b，直到 a ^ b> max_limit

此方法的诀窍是仅测试质数

的值

这种方法的诀窍不是测试完美幂的 a 值(例如，不要测试 4、8、9 等(

相关文章：