Factors and Factorials

All of you are familiar with factorial of a number. The factorial of a number N is defined as the product of all integers from 1 to N. Mathematically it is defined as 1! = 1 and N! = N*(N-1)! But there is a problem with this, if go for higher values of N, factorials grow very rapidly as 6! = 720, 11! = 39916800. We can specify such large numbers with the help of their prime factors. For example: 100 can be written as (2 2 5 2), means there is 2 two and 2 five is present in 100.

Again we are left with another problem. To find the prime factors of such large numbers is very tedious task. So I want help from you people to solve this problem. Write a code that takes an input any positive integer N and gives output of N!’s prime factor representation.

 

Input 

Input will consist of a series of lines, each line containing a single integer N (2<=N<1000). The file will be terminated by a line consisting of a single 0.

 

Output 

Output will consist of prime factor representation of N! There will be a blank line between two consecutive outputs.

 

Sample Input 

5                                                                                                                                    

7                                                                                                                                    

0

 

Sample Output 

2 3

3 1

5 1

 

2 4

3 2

5 1

7 1

 

using System;

using System.Collections.Generic;

using System.Collections;

using System.Linq;

using System.Text;

using System.Diagnostics;

 

namespace PrimeFactorial

{

    class Program

    {

        static void Main(string[] args)

        {

            int fact = 7;

            ArrayList primeFactors = new ArrayList();

            for (int iter = 2; iter <= fact; iter++)

            {

                if (!IsPrime(iter))

                {

                    ArrayList temp = PrimeFactors(iter);

                    for (int i = 0; i < temp.Count; i++)

                    {

                        primeFactors.Add(temp[i]);

                    }

                }

                else

                {

                    primeFactors.Add(iter);

                }

            }

            primeFactors.Sort();

            int counter = 1;

            for (int iter = 0; iter < primeFactors.Count; iter++)

            {

                if (iter + 1 != primeFactors.Count)

                {

                    if ((int)primeFactors[iter] == (int)primeFactors[iter + 1])

                    {

                        counter++;

                    }

                    else

                    {

                        Console.WriteLine(primeFactors[iter] + " " + counter);

                        counter = 1;

                    }

                }

                else

                {

                    Console.WriteLine(primeFactors[iter] + " " + counter);

                }

            }

        }

        public static bool IsPrime(int num)

        {

            if (num <= 1)

            {

                return false;

            }

            else if (num == 2)

            {

                return true;

            }

            else

            {

                for (int i = 2; i < num; i++)

                {

                    if (num % i == 0)

                    {

                        return false;

                    }

                }

                return true;

            }

        }

        public static ArrayList PrimeFactors(int num)

        {

            ArrayList primeFactors = new ArrayList();

            for (int i = 2; i <= num; i++)

            {

                if (IsPrime(i) && num % i == 0)

                {

                    primeFactors.Add(i);

                    num = num / i;

                    i = 1;

                }

            }

            return primeFactors;

        }

    }

}

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s