What is prime factorization?

Question

I have this for homework but i dont quite get it.

Answer 1

"Prime Factorization" is finding which prime numbers you need to multiply together to get the original number.  

Answer 2

Everything is from the website: I just cut out what would be beneficial to you.

First, you must know what a factor is. In general terms, a factor is a whole number, not including 1, which goes into a number evenly (that is, with no remainder).

Second, you must know that a prime number is a number that has two and only two factors, which are one, and itself. Take the number 3. It is only divisible by 1 and 3, so it is prime.

The number four, on the other hand, can be divided by 1, 4, but also 2, (it has three factors) so it is not prime.Here is an important point: The number 1 is generally not considered a prime number. Why? Because the definition of a prime is that has two and only two factors. But the number 1 has only 1 factor, which is 1. Therefore it doesn't fit the definition of a prime number.

One good thing about that is that it keeps us from always having to use 1 in the solution for prime factors of number. It is simply assumed that 1 is a factor of all whole numbers (which it is) but it would be redundant to include it in every solution for primes, so we don't.

Prime factors are the factors of a number that also happen to be prime.

Take the number 30. What numbers go into 30 evenly (besides one and itself)?

2 goes in evenly, 3 goes in evenly, 5 goes in evenly, 10 goes in evenly, and 15 goes in evenly. But 10 and 15 are not prime numbers, so they are not prime factors of 30 (or anything else!)

So 2, 3 and 5 are prime factors of 30.

Prime factorization also requires us to tell how many times each of those prime factors go into a number, along with the other prime factors.

Take the prime factors, and multiply them by themselves

2 x 3 x 5 = 30. So you only need one of each to have the prime factorization of 30.

But if I had the number, say, 40, we'd have the prime factors:

2, and 5. (all other factors of 40 are not prime).

But 2 x 5 is not 40.

So how can we get 40 with just twos and fives?

Well, we'd need 2 x 2 x 2 x 5 to make 40. (That's the same as 8 x 5).

A simpler way to write 2 x 2 x 2 x 5 is to write 2 ^3 x 5 (which is read, "Two to the third power times 5.")

So the prime factors of 40 are 2 and 5, but the prime factorization of 30 is 2^3 x 5. An easy recipe to prime factorize a number is this:

List the prime factors. To do this, start with 2, see if that will go into the number. If it does go in, divide the number by 2.

Now you have a new number. Repeat the above step until 2 will no longer go into the number evenly.

For the answer so far, write the number 2 (if it actually does go into the original number at all) and after the caret (the ^) write the amount of times it went in.

Then use the next highest prime number, which is 3, and repeat the above steps with the number 3.

After that use the next highest prime number and repeat the above. (The next highest prime number is not 4!)

Answer 3

The factorization of a number into its constituent primes, also called prime decomposition. Given a positive integer , the prime factorization is written



where the s are the  prime factors, each of order . Each factor  is called a primary. Prime factorization can be performed in Mathematica using the command FactorInteger[n], which returns a list of  pairs.

Through his invention of the Pratt certificate, Pratt (1975) became the first to establish that prime factorization lies in the complexity class NP.

The following Mathematica code can be used to give a nicely typeset form of a number :

The first few prime factorizations (the number 1, by definition, has a prime factorization of "1") are given in the following table.

prime factorization  prime factorization

1 1 11 11

2 2 12  

3 3 13 13

4  14  

5 5 15  

6  16  

7 7 17 17

8  18  

9  19 19

10  20  

The number of digits in the prime factorization of , 2, ..., are 1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 2, 3, (Sloane's A050252).

In general, prime factorization is a difficult problem, and many sophisticated prime factorization algorithms have been devised for special types of numbers.

Integers can also be factored over the Gaussian primes. For example, the following table gives the Gaussian integer factorizations for the first few positive integers.

factorization

1 1

2  

3 3

4  

5  

6  

7 7

8  

9  

10  

Interestingly, prime numbers  equal to 1 (mod 4) can always by factored into Gaussian primes in the form



where the real and imaginary parts are inverted in the two parts, while prime numbers equal to 3 (mod 4) cannot be factored into Gaussian primes. This is directly related to Fermat's 4n+1 theorem.

Answer 4

Factorisation sounds a bit rude to me. Does your mother know you use that sort of language?