Perfect Powers check

Question

A perfect power is a number N where A^B = N (A >= 1 , B >= 2)

This is my code. I'm trying to find how many of these numbers exist between 1 and the top limit I select.

    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;
            }
        }
     } 

It's currently working. Sadly it becomes quite slow after around 1,000,000 checks. Anyhow to improve this algorithm's speed?

Answer 1

Math.Log is expensive, Math.Pow is expensive, doubles are expensive. You know what isn't expensive? Multiplying integers.

Some theorycrafting: if A^B == n and n<10^9 and B>=2 than max A is close to 5*10^4. So lets have a set of perfect powers. Iterate from 2 while i*i<=max_n, if i is not in set, add i*i, i*i*i, and so on while its less then max_n. If A=C^D, then A^B = C^(B*D), and is already in set.

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);
    }

EDIT: This runs less then half a second on debug on my laptop.

Answer 2

Move Math.Log(Number, 2) + 1 out of the for loop.

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