找到给定数字因子的算法..最短方法？

Question

找出给定数字的因子可能是最简单和最有效的逻辑.是否存在基于相同的算法.

实际上,我真正的问题是找出答案.对于给定数字存在的因素..

所以任何算法,请告诉我这个..

谢谢.

Answer 1

实际上,我真正的问题是找出答案.对于给定数字存在的因素..

嗯,这是不同的.我们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);
    }
}

在我的机器上的结果:

测试等价......
等价确认!
时间IVlad ...
总毫秒数:2448
Timing Maciej ...
总毫秒数:3951
按任意键继续...

Answer 2

有大量可用的算法 - 从简单的试验设计到非常复杂的大数算法。查看Wikipedia 上的整数因式分解并选择适合您需求的一个。

这是一个简短但低效的 C# 实现，用于查找素数因子的数量。如果您需要因子的数量（不是质因子），则必须存储质因子及其重数，然后计算因子的数量。

var number = 3 * 3 * 5 * 7 * 11 * 11;

var numberFactors = 0;
var currentFactor = 2;

while (number > 1)
{
    if (number % currentFactor == 0)
    {
        number /= currentFactor;
        numberFactors++;
    }
    else
    {
        currentFactor++;
    }
}