查找给定数字因子的算法。最短方法？

2023-05-22 14:29

实际上，我真正的问题是找出编号。给定数字存在的因素

好吧，这是不同的。设n给定数字。

如果n = p1^e1 * p2^e2 * ... * pk^ek，其中每个p都是质数，则的因子个数n为(e1 + 1)*(e2 + 1)* ... *(ek + 1)。更多关于此这里。

因此，找到每个素因出现的幂就足够了。例如：

read given number in n
initial_n = n
num_factors = 1;
for (i = 2; i * i <= initial_n; ++i) // for each number i up until the square root of the given number
{
    power = 0; // suppose the power i appears at is 0
    while (n % i == 0) // while we can divide n by i
    {
        n = n / i // divide it, thus ensuring we'll only check prime factors
        ++power // increase the power i appears at
    }
    num_factors = num_factors * (power + 1) // apply the formula
}

if (n > 1) // will happen for example for 14 = 2 * 7
{
    num_factors = num_factors * 2 // n is prime, and its power can only be 1, so multiply the number of factors by 2
}

例如，以18。18 = 2^1 * 3*2 => number of factors = (1 + 1)*(2 + 1) = 6。确实，的6因素18是1, 2, 3, 6, 9, 18。

这是我的方法与@Maciej描述和发布的方法之间的一些基准。他的优点是易于实现，而我的优点是更改（仅对质数进行迭代）更快，如我对此测试所做的那样：

 class Program
{
    static private List<int> primes = new List<int>();

    private static void Sieve()
    {
        bool[] ok = new bool[2000];

        for (int i = 2; i < 2000; ++i) // primes up to 2000 (only need up to sqrt of 1 000 000 actually)
        {
            if (!ok[i])
            {
                primes.Add(i);

                for (int j = i; j < 2000; j += i)
                    ok[j] = true;
            }
        }
    }

    private static int IVlad(int n)
    {
        int initial_n = n;
        int factors = 1;

        for (int i = 0; primes[i] * primes[i] <= n; ++i)
        {
            int power = 0;
            while (initial_n % primes[i] == 0)
            {
                initial_n /= primes[i];
                ++power;
            }
            factors *= power + 1;
        }

        if (initial_n > 1)
        {
            factors *= 2;
        }

        return factors;
    }

    private static int Maciej(int n)
    {
        int factors = 1;
        int i = 2;
        for (; i * i < n; ++i)
        {
            if (n % i == 0)
            {
                ++factors;
            }
        }

        factors *= 2;

        if (i * i == n)
        {
            ++factors;
        }

        return factors;
    }

    static void Main()
    {
        Sieve();


        Console.WriteLine("Testing equivalence...");

        for (int i = 2; i < 1000000; ++i)
        {
            if (Maciej(i) != IVlad(i))
            {
                Console.WriteLine("Failed!");
                Environment.Exit(1);
            }
        }

        Console.WriteLine("Equivalence confirmed!");

        Console.WriteLine("Timing IVlad...");
        Stopwatch t = new Stopwatch();

        t.Start();
        for (int i = 2; i < 1000000; ++i)
        {
            IVlad(i);
        }

        Console.WriteLine("Total milliseconds: {0}", t.ElapsedMilliseconds);
        Console.WriteLine("Timing Maciej...");

        t.Reset();
        t.Start();
        for (int i = 2; i < 1000000; ++i)
        {
            Maciej(i);
        }


        Console.WriteLine("Total milliseconds: {0}", t.ElapsedMilliseconds);
    }
}

我的机器上的结果：