Prime Factors

Webster defines prime as:

prime () n. [ME, fr. MF, fem. of prin first, L primus; akin to L prior] 1 : first in time; original 2 a : having no factor except itself and one ❤ is a ~ number> b : having no common factor except one <12 and 25 are relatively ~> 3 a: first in rank, authority or significance : principal b : having the highest quality or value <~ television time> [from Webster’s New Collegiate Dictionary]

The most relevant definition for this problem is 2a: An integer g > 1 is said to be prime if and only if its only positive divisors are itself and one (otherwise it is said to be composite). For example, the number 21 is composite; the number 23 is prime. Note that the decomposition of a positive number g into its prime factors, i.e.,

g = f1 × f2 × … × fn

is unique if we assert that fi > 1 for all i and fi <= fj for i < j.

One interesting class of prime numbers are the so-called Mersenne primes which are of the form 2p – 1. Euler proved that 231 – 1 is prime in 1772 — all without the aid of a computer.

Input

The input will consist of a sequence of numbers. Each line of input will contain one number g in the range -231 < g < 231. The end of input will be indicated by an input line having a value of zero.

Output

For each line of input, your program should print a line of output consisting of the input number and its prime factors. For an input number 0 < g = f1 × f2 × … × fn, where each fi is a prime number greater than unity (with fi <= fj for i < j), the format of the output line should be

<g> = < f1 > × < f2 > × … × < fn >

If 0 > g = f1 × f2 × … × fn, the format of the output line should be

<g> = -1 × < f1 > × < f2 > × … × < fn >

Sample Input

-190

-191

-192

-193

-194

195

196

197

198

199

200

0

Output for the Sample Input

-190 = -1 x 2 x 5 x 19

-191 = -1 x 191

-192 = -1 x 2 x 2 x 2 x 2 x 2 x 2 x 3

-193 = -1 x 193

-194 = -1 x 2 x 97

195  = 3 x 5 x 13

196  = 2 x 2 x 7 x 7

197  = 197

198  = 2 x 3 x 3 x 11

199  = 199

200  = 2 x 2 x 2 x 5 x 5

 

using System;

using System.Collections.Generic;

using System.Text;

using System.Collections;

 

namespace ConsoleApplication1

{

    class Program

    {

        static void Main(string[] args)

        {

            int num = -192;

            ArrayList primeFactors = new ArrayList();

            primeFactors = PrimeFactors(Math.Abs(num));

            Console.Write(num + " = ");

            if (num < 0)

            {

                Console.Write("-1" + " X ");

            }

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

            {

                if (i != primeFactors.Count – 1)

                {

                    Console.Write(primeFactors[i] + " X ");

                }

                else

                {

                    Console.Write(primeFactors[i]);

                }

            }

            Console.WriteLine();

        }

        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;

        }

        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;

            }

        }

    }

}

 

-192 = -1 X 2 X 2 X 2 X 2 X 2 X 2 X 3
Press any key to continue . . .

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