Algorithm to find the factors of a given Number.. Shortest Method?

What could be the simplest and time efficient logic to find out the factors of a given Number. Is there any algorithm that exist, based on the same.

Actually, my real problem is to find out the no. of factors that ex开发者_StackOverflow中文版ist for a given Number..

So Any algorithm, please let me know on this..

Thanks.

Actually, my real problem is to find out the no. of factors that exist for a given Number..

Well, this is different. Let n be the given number.

If n = p1^e1 * p2^e2 * ... * pk^ek, where each p is a prime number, then the number of factors of n is (e1 + 1)*(e2 + 1)* ... *(ek + 1). More on this here.

Therefore, it is enough to find the powers at which each prime factor appears. For example:

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
}

For example, take 18. 18 = 2^1 * 3*2 => number of factors = (1 + 1)*(2 + 1) = 6. Indeed, the 6 factors of 18 are 1, 2, 3, 6, 9, 18.

Here's a little benchmark between my method and the method described and posted by @Maciej. His has the advantage of being easier to implement, while mine has the advantage of being faster if change to only iterate over the prime numbers, as I have done for this test:

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

Results on my machine:

Testing equivalence...
Equivalence confirmed!
Timing IVlad...
Total milliseconds: 2448
Timing Maciej...
Total milliseconds: 3951
Press any key to continue . . .

There is a large number of algorithms available - from simple trial devision to very sophisticated algorithms for large numbers. Have a look at Integer Factorization on Wikipedia and pick one that suits your needs.

Here is a short but inefficient C# implementation that finds the number of prime factors. If you need the number of factors (not prime factors) you have to store the prime factors with their multiplicity and calculate the number of factors afterwards.

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

Here is a fruit of my short discussion with |/|ad :)

read given number in n
int divisorsCount = 1;
int i;
for(i = 2; i * i < n; ++i)
{
    if(n % i == 0)
    {
        ++divisorsCount;
    }
}
divisorsCount *= 2;
if(i * i == n)
{
    ++divisorsCount;
}

Careful, this answer is not useful/fast for a single value of n.

Method 1:

You can get it in O(polylog(n)) if you maintain a look-up table (for the first prime factor of a number).

If gcd(a,b) == 1, then no. of factors of a*b = (no. of factors of a) * (no. of factors of b)

Therefore, for a given number a*b, if gcd(a,b) != 1 then we can have two other numbers p and q where p = a and q = b/gcd(a,b). Thus, gcd(p,q) == 1. Now, we can recursively find the number of factors for p and q.

It will take only some small amount of efforts to ensure neither p nor q is 1.

P.S. This method is also useful when you need to know the number of factors of all numbers from 1 to n. It would be an order of O(nlogn + O(look-up table)).

Method 2: (I do not have ownership for this.)

If you have the look-up for first prime factor till n, then you can know it's all prime factors in O(logn) and thus find the number of factors from them.

P.S. Google 'Factorization in logn' for better explanation.

Euclid's Algorithm should suffice.