Prime Factorization Calculator
Decompose positive integers into their prime factors. Essential for number theory, cryptography, and understanding the fundamental building blocks of numbers.
Factorize a Number
Enter a positive integer to find its prime factors:
Every integer greater than 1 can be uniquely represented as a product of prime numbers.
Understanding Prime Factorization
Prime factorization is the process of breaking down a composite number into its prime factors. This is fundamental to number theory and has important applications in cryptography, computer science, and mathematics.
The Fundamental Theorem of Arithmetic
Every integer greater than 1 can be uniquely represented as a product of prime numbers, up to the order of the factors. This theorem forms the foundation of prime factorization.
๐ข Prime Numbers
Numbers greater than 1 with no positive divisors other than 1 and themselves.
Examples: 2, 3, 5, 7, 11, 13, 17, 19...
๐ Composite Numbers
Numbers that can be factored into smaller integers greater than 1.
Examples: 4, 6, 8, 9, 10, 12, 14...
โก Prime Factors
The prime numbers that multiply together to give the original number.
The "building blocks" of composite numbers.
The Factorization Algorithm
Step 1: Divide by 2
Repeatedly divide the number by 2 until it's no longer divisible by 2.
Count how many times 2 divides the number.
Step 2: Odd Factors
Test odd numbers from 3 up to โn.
Divide by each odd factor until no longer divisible.
Step 3: Final Check
If the remaining number is greater than 1, it's a prime factor.
This handles cases where n itself is prime.
Example Factorizations
| Number | Prime Factors | With Exponents | Explanation |
|---|---|---|---|
| 12 | 2 ร 2 ร 3 | 2ยฒ ร 3ยน | 12 = 4 ร 3, and 4 = 2 ร 2 |
| 24 | 2 ร 2 ร 2 ร 3 | 2ยณ ร 3ยน | 24 = 8 ร 3, and 8 = 2 ร 2 ร 2 |
| 30 | 2 ร 3 ร 5 | 2ยน ร 3ยน ร 5ยน | 30 = 2 ร 3 ร 5 (three distinct primes) |
| 36 | 2 ร 2 ร 3 ร 3 | 2ยฒ ร 3ยฒ | 36 = 6 ร 6, and 6 = 2 ร 3 |
| 48 | 2 ร 2 ร 2 ร 2 ร 3 | 2โด ร 3ยน | 48 = 16 ร 3, and 16 = 2โด |
| 60 | 2 ร 2 ร 3 ร 5 | 2ยฒ ร 3ยน ร 5ยน | 60 = 4 ร 3 ร 5, and 4 = 2ยฒ |
| 72 | 2 ร 2 ร 2 ร 3 ร 3 | 2ยณ ร 3ยฒ | 72 = 8 ร 9, and 8 = 2ยณ, 9 = 3ยฒ |
| 100 | 2 ร 2 ร 5 ร 5 | 2ยฒ ร 5ยฒ | 100 = 4 ร 25, and 4 = 2ยฒ, 25 = 5ยฒ |
Number Properties from Prime Factors
๐ Perfect Squares
A number is a perfect square if all exponents in its prime factorization are even.
Example: 36 = 2ยฒ ร 3ยฒ is a perfect square.
๐ Perfect Cubes
A number is a perfect cube if all exponents are multiples of 3.
Example: 27 = 3ยณ is a perfect cube.
๐ข Number of Divisors
For prime factorization pโแต ร pโแต ร pโแถ ร ..., the number of divisors is (a+1)ร(b+1)ร(c+1)ร...
Example: 12 = 2ยฒ ร 3ยน has (2+1)ร(1+1) = 6 divisors: 1, 2, 3, 4, 6, 12
Practical Applications
๐ Cryptography
RSA encryption relies on the difficulty of factoring large numbers.
Prime factorization is computationally expensive for large numbers.
๐งฎ GCD & LCM
Greatest Common Divisor and Least Common Multiple can be found from prime factorizations.
Essential for fraction operations and number theory.
๐ป Computer Science
Data compression, hash functions, and random number generation use prime factors.
Important for efficient algorithms and data structures.
๐ Mathematics Education
Understanding number properties, divisibility rules, and mathematical relationships.
Foundation for advanced topics in algebra and number theory.
Cryptographic Applications
๐ RSA Algorithm
Public-key cryptography uses large prime numbers.
The security depends on the difficulty of factoring large composite numbers.
๐ Key Generation
Cryptographic keys are generated using prime factorization.
Large prime numbers are crucial for secure encryption.
๐ก๏ธ Digital Signatures
Digital signature algorithms use properties of prime factors.
Ensures authenticity and integrity of digital messages.
Step-by-Step Factorization Example
Factorize 84
1. 84 รท 2 = 42
2. 42 รท 2 = 21
3. 21 รท 3 = 7
4. 7 is prime
Result: 84 = 2ยฒ ร 3ยน ร 7ยน
Factorize 120
1. 120 รท 2 = 60
2. 60 รท 2 = 30
3. 30 รท 2 = 15
4. 15 รท 3 = 5
5. 5 is prime
Result: 120 = 2ยณ ร 3ยน ร 5ยน
Factorize 169
1. 169 is odd, skip 2
2. 169 รท 13 = 13
3. 13 is prime
Result: 169 = 13ยฒ
Historical Significance
The concept of prime numbers and factorization has been studied for thousands of years. Ancient Greek mathematicians like Euclid proved fundamental theorems about primes. The development of modern cryptography in the 20th century brought prime factorization to practical importance in computer security.
๐ก Interesting Fact: The largest known prime number has over 24 million digits! Finding such large primes and factoring large composite numbers are active areas of research in mathematics and computer science.