Factorizing largest number

Question

here is sample code

public static decimal factorization(decimal num, decimal factor)
        {

            if (num == 1)
            {
                return 1;
            }
            if ((num % factor)!= 0)
            {

                while(num% factor != 0)
                {
                    factor++;
                }

            }

            factors.Add(factorization(num / factor, factor));
            return factor;

        }

Note : I have initialize factors as global.

Above code will work fine for sample inputs 90 , 18991325453139 but will not work for input 12745267386521023 ... so how can I do that ? How can I achieve this efficiently ... I know recursive call will consume memory that's why I have checked the last input using without recursion .. But its not working too

Answer 1

You can use that if

factor*factor > num

then num is prime

It will decrease complexity from O(n) to O(sqrt(n))

EDIT

while(num% factor != 0)
{
    factor++;
    if(factor*factor>num){ // You can precalc sqrt(num) if use big arifmetic
        factor=num; //skip factors between sqrt(num) and num;
    }
}

Answer 2

using System.Collections;  

      public static int[] PrimeFactors(int num)  
       {  
           ArrayList factors = new ArrayList();  

           bool alreadyCounted = false;  
           while (num % 2 == 0)  
           {  
               if (alreadyCounted == false)  
               {  
                   factors.Add(2);  
                   alreadyCounted = true;  
               }  
               num = num / 2;  
           }  

           int divisor = 3;  
           alreadyCounted = false;  
           while (divisor <= num)  
           {  
               if (num % divisor == 0)  
               {  
                   if (alreadyCounted == false)  
                   {  
                       factors.Add(divisor);  
                       alreadyCounted = true;  
                   }  
                   num = num / divisor;  
               }  
               else  
               {  
                   alreadyCounted = false;  
                   divisor += 2;  
               }  
           }  

           int[] returnFactors = (int[])factors.ToArray(typeof(int));  

           return returnFactors;  
       }  

I just copied and posted some code from Smokey Cogs because this is a very common problem.

The code does some things better than yours.

First you divide by two until the number is no longer even. From there, you can start with 3 and increment by 2 (skip every even number) since all the 2's have been factored out.

Nonetheless, there are ways to improve. Think about the usage of "alreadyCounted" in the code. Is it absolutely essential? For example, using

    if (num % 2 == 0)
{
        factors.Add(2);
        num = num/2;
}

    while( num %2 == 0)
        {num = num/2;}

Allows you to skip the extra comparisons in the beginning.

RiaD also gave a great heuristic that factor^2 > num implies that num is prime. This is because (sqrt(n))^2 = n, so the only number after sqrt(n) that divides num will be num itself, once you've taken out the previous primes.

Hope it helps!

Answer 3

To see how to find the factors of a given number in C# see this (duplicate?) StackOverflow question.

A few points on your code:

• there is no need for recursion if using a naive search, just build a list of factors within the method and return it at the end (or use yield).
• your second if statement is redundant as it wraps a while loop with the same condition.
• you should use an integer type (and unsigned integer types will allow larger numbers than their signed counterparts, e.g. uint or ulong) rather than decimal as you are working with integers. For arbitrarily large integers, use System.Numerics.BigInteger.
• if you search incrementally upwards for a factor, you can stop looking when you have got as far as the square root of the original number, as no factor can be larger than that.

Also, note that there is no known efficient algorithm for factoring large numbers (see Wikipedia for a brief overview).

Here's example code, based on the above observations:

static IList<BigInteger> GetFactors(BigInteger n)
{
    List<BigInteger> factors = new List<BigInteger>();
    BigInteger x = 2;
    while (x <= n)
    {
        if (n % x == 0)
        {
            factors.Add(x);
            n = n / x;
        }
        else
        {
            x++;
            if (x * x >= n)
            {
                factors.Add(n);
                break;
            }
        }
    }
    return factors;
}

Note that this is still a rather naive algorithm which could easily be further improved.