Jump to content

User:JustBerry/Math/Prime Factorization/sandbox

From Wikipedia, the free encyclopedia

Status: Work In Progress

[http://en.wikipedia.org/wiki/Integer_factorization]

Prime decomposition

[edit]
This image demonstrates the prime decomposition of 864. A shorthand way of writing the resulting prime factors is
Finding the prime factorization of 42 via the 'Factor Tree method'

By the fundamental theorem of arithmetic, every positive integer has a unique prime factorization. (A special case for 1 is not needed using an appropriate notion of the empty product.) However, the fundamental theorem of arithmetic gives no insight into how to obtain an integer's prime factorization; it only guarantees its existence.

Given a general algorithm for integer factorization, one can factor any integer down to its constituent prime factors by repeated application of this algorithm. However, this is not the case with a special-purpose factorization algorithm, since it may not apply to the smaller factors that occur during decomposition, or may execute very slowly on these values. For example, if N is the number (2521 − 1) × (2607 − 1), then trial division will quickly factor 10N as 2 × 5 × N, but will not quickly factor N into its factors.

When a prime factorization has the same prime factor (f) appearing x number of times in a prime factorization, the factors can be written as fx. There are several methods to performing a prime factorization. The "factor tree" method is one of the methods used to find a prime factorization. It represents the prime factors of a positive integer in a "family tree" layout or diagram.[1]


External Link(s)

[edit]

Prime Factorization Instructional Video

Reference(s)

[edit]
  1. ^ "What is a Factor Tree?". Factor Tree. Retrieved 28 May 2013. {{cite web}}: |first= has generic name (help); |first= missing |last= (help)