Question Programme for factorization

[aindrea]

As I am learning C#, I have just written a programme which has the goal to read an integer in order to do prime factorization with it. So if it reads 49, the output is supposed to be 7 7. If it reads 8, the output is supposed to be 2 2 2

Here it is:

  using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;

namespace ConsoleApp1
{
    class Program
    {
        private static ArrayList primes = new ArrayList();
        private static ArrayList primes2 = new ArrayList();
        private static ArrayList nonPrimes = new ArrayList();
        private static ArrayList numbersToRemove = new ArrayList();

        static void Main(string[] args)
        {
            Console.WriteLine("I want to do prime factorization with the natural number you enter; it still does not work as intended.");
           var input = Console.ReadLine();
            int number = 0;
            try
            {
                number = Int32.Parse(input);
            }
            catch(System.FormatException)
            {
                Console.WriteLine("Please write a natural number, don't write a decimal or any gibberish.");
            }
            catch (System.OverflowException)
            {
                Console.WriteLine("The number you entered is so big that I cannot parse it.");
            }
                string res = factorize(number);
                Console.WriteLine(res);
                Console.WriteLine("Press any key to stop."); 
                Console.ReadLine();
        }

        ////////////////////////////////////////////////////////////////////////////////////////////////////

        private static string factorize(int number)
        {

            if (isPrime(number)) {
                primes.Add(number);
                return string.Join(" ", primes.ToArray());
            }

            for (double i = 2; i < number; i++) {

                if (isNatural((double)number / i) && !isPrime((int)(number / i)))
                {
                    nonPrimes.Add((double)number / i);
                }
                if (isNatural((double)number / i) && isPrime((int)(number / i)))
                {
                    primes.Add((double)number / i);
                }
            }

            foreach (double n in nonPrimes) {
                foreach (double p in primes) {
                    if(!isNatural(n / p)) {
                        numbersToRemove.Add(p);//Add these numbers to a List numbersToRemove, 
                    }
                }
            }

            foreach (double v in primes)
            {
                primes2.Add(v);
            }

            foreach (double r in numbersToRemove) {//And remove them from the original list.
                primes2.Remove(r);
            }

            return string.Join(" ", primes.ToArray()) + " " + string.Join(" ", primes2.ToArray());
        }

        ////////////////////////////////////////////////////////////////////////////////////////////////////


        private static bool isNatural(double v)
        {
            return (v % 1) == 0;
        }

        private static bool isPrime(int numberToTest)
        {
            if (numberToTest == 1 && numberToTest == 2){
                return true;
            }
            for (double d=2.0;d<numberToTest;d++){
                if (numberToTest % d == 0){
                    return false;
                }
            }
            return true;
        }
    }

    /*
    internal class ReverseSort : IComparer
    {
        public int Compare(object x, object y)
        {
            return Comparer.Default.Compare(y, x);
        }
    }
    */
}

My question is: This seems to work for some numbers (like 49, 11, 12) but it does not work for e. g. 144. What is the cause of this?

 

[jmcilhinney]

I imagine that there are algorithms you can follow to achieve your goal. You should start there and attempt to implement an algorithm in C# code. If you then show us the code and the algorithm it is supposed to implement, we can tell you whether there is a better way to implement each specific step than the way you've done it.

 

[aindrea]

Even though I didn't stumble over an alogorithm on the net, I seem to have found out:

using System;
using System.Collections;

namespace ConsoleApp1
{
    class Program
    {
        private static ArrayList primes = new ArrayList();
        private static ArrayList primeFactors = new ArrayList();
        private static ArrayList resArr = new ArrayList();

        static void Main(string[] args)
        {
           Console.WriteLine("I can do prime factorization with the natural number you enter.");
           var input = Console.ReadLine();
           int numberEntry = 0;
            //Here, exceptions are handled that might arise for example when something wrong is entered.
            try
            {
                numberEntry = Int32.Parse(input);

            } catch(System.FormatException)
            {
            Console.WriteLine("Please write a natural number, don't write a decimal or any gibberish.");
            } catch (System.OverflowException)
            {
            Console.WriteLine("The number you entered is so big that I cannot parse it.");
            }
               factorizeEntry(numberEntry);
        }

        /// <summary>
        /// Calls all necessary methods to do the factorization and to write the result into the console.
        /// </summary>
        /// <param name="number"></param>
        private static void factorizeEntry(int number)
        {
            //All existing prime factors for a number end up in an ArrayList.
            var res = seekPrimeFactors(number);
            foreach (int p in res)
            {
                if (isNatural((double)number / p))
                {
                    primeFactors.Add(p);
                }
            }
            //...and now let us sort these.
            primeFactors.Sort();

            int index = primeFactors.Count - 1;
            while (index > 0)
            {
                //Take the prime factors, divide them by number, and then the ratio is a number, the prime factor gets printed or added to res.
                if (isNatural((double)((double)number / (int)primeFactors[index])))
                {
                    //Console.WriteLine(primeFactors[index]);
                    resArr.Add(primeFactors[index]);
                    number = (number / (int)primeFactors[index]);
                }

                //As soon as the division no longer works, let's grab the next smaller prime factor. 
                if (!isNatural((double)((double)number / (int)primeFactors[index])))
                {
                    index--;
                }
            }

            Console.WriteLine(string.Join(" ", resArr.ToArray()));
            Console.WriteLine("Press any key to stop.");
            Console.ReadLine();
        }

        /// <summary>
        /// Gives us an ArrayList with all prime numbers to be found in a given number.
        /// </summary>
        /// <param name="number"></param>
        /// <returns></returns>
        private static ArrayList seekPrimeFactors(int number)
        {
            if (isPrime(number)) {
                primes.Add(number);                
            }
            if (number == 1) {
                primes.Sort(new ReverseSort());
                return primes;
            }
                return seekPrimeFactors(number-1); 
        }

        /// <summary>
        /// Gives us the answer if a given number is natural or not (natural without 0)
        /// </summary>
        /// <param name="numToTest"></param>
        /// <returns></returns>
        private static bool isNatural(double numToTest)
        {
            return (numToTest % 1) == 0;
        }

        /// <summary>
        /// Gives us the answer if a given number is a prime number.
        /// </summary>
        /// <param name="numberToTest"></param>
        /// <returns></returns>
        private static bool isPrime(int numberToTest)
        {
            if (numberToTest == 1 && numberToTest == 2){
                return true;
            }
            for (double d=2.0;d<numberToTest;d++){
                if (numberToTest % d == 0){
                    return false;
                }
            } return true;
        }
    }

    internal class ReverseSort : IComparer
    {
        public int Compare(object x,object y)
        {
            return Comparer.Default.Compare(y,x);
        }
    }
}

 

[aindrea]

Now I have changed the logic of the factorizeENtry()-method. I still don't understand why it does not factorize number after number after number. I just want to call the method from within itself but after that happens, it somehow clogs. What coulöd be the cause of this?

       /// <summary>
        /// Calls all necessary methods to do the factorization and to write the result into the console.
        /// </summary>
        /// <param name="number"></param>
        private static void factorizeEntry()
        {


                Console.WriteLine("I can do prime factorization with the natural number you enter.");
                var input = Console.ReadLine();
                int number = 0;
                //Here, exceptions are handled that might arise for example when something wrong is entered.
                try
                {
                    number = Int32.Parse(input);


                }
                catch (System.FormatException)
                {
                    Console.WriteLine("Please write a natural number, don't write a decimal or any gibberish.");
                }
                catch (System.OverflowException)
                {
                    Console.WriteLine("The number you entered is so big that I cannot parse it.");
                }




                //All existing prime factors for a number end up in an ArrayList.
                var res = seekPrimeFactors(number);
                foreach (int p in res)
                {
                    if (isNatural((double)number / p))
                    {
                        primeFactors.Add(p);
                    }
                }
                //...and now let us sort these.
                primeFactors.Sort();


                int index = primeFactors.Count - 1;
                while (index > 0)
                {
                    //Take the prime factors, divide them by number, and then the ratio is a number, the prime factor gets printed or added to res.
                    if (isNatural((double)((double)number / (int)primeFactors[index])))
                    {
                        //Console.WriteLine(primeFactors[index]);
                        resArr.Add(primeFactors[index]);
                        number = (number / (int)primeFactors[index]);
                    }


                    //As soon as the division no longer works, let's grab the next smaller prime factor. 
                    if (!isNatural((double)((double)number / (int)primeFactors[index])))
                    {
                        index--;
                    }
                }


                Console.WriteLine(string.Join(" ", resArr.ToArray()));
                Console.WriteLine("Press s to stop or press any other key if you want to continue.");
                string stopEntry = Console.ReadLine();
            if (stopEntry.Equals("s"))
            {
                Environment.Exit(0);
            }
            else { factorizeEntry(); }
        }

 

[jmcilhinney]

Have you debugged it properly, i.e. set a breakpoint and stepped through the code? If you have then you should be able to describe exactly where and how the behaviour of the code differs from your expectation. If you have then you should do that now. If you don't know how, you should start learning here:

https://msdn.microsoft.com/en-us/library/y740d9d3.aspx?f=255&MSPPError=-2147217396

 

[aindrea]

Thank you very much for your advice. I debugged it and I could fix the problem by calling the Clear() method on all three static arrays both before calling the factorizeEntry()-method again and in each of the catch-blocks.