Free Prime Number & Factor Calculators
Check primality, factorize numbers, compute GCD/LCM, and more. Simple, fast, and free.
Quick Answer
A prime number is only divisible by 1 and itself. Quick check: if no integer from 2 to √n divides n evenly, n is prime.
Example: 97 is prime (√97 ≈ 9.8, not divisible by 2, 3, 5, 7)
Choose a Category
Popular Tools
About PrimeCalc
PrimeCalc provides free, fast, and accurate number theory tools for students, educators, and curious minds. Check primes, factorize integers, compute GCD and LCM, and more — all instant, no registration required.
What Makes a Number Prime?
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Two is the only even prime; all other even numbers are composite (divisible by 2). To check whether a number n is prime, it suffices to test divisibility by all primes up to √n — if none divide evenly into n, then n is prime. There are infinitely many primes (proved by Euclid around 300 BC), but they become increasingly sparse at larger values. The prime number theorem approximates the count of primes up to n as n ÷ ln(n).
Prime Factorization and the Fundamental Theorem of Arithmetic
Every integer greater than 1 can be expressed as a unique product of prime numbers — this is the Fundamental Theorem of Arithmetic. For example: 360 = 2³ × 3² × 5. Prime factorization is the process of finding this representation. The trial division method divides the number repeatedly by the smallest prime that divides it. Efficient algorithms for large numbers include the Pollard rho algorithm and the General Number Field Sieve (GNFS). Prime factorization underpins RSA encryption: multiplying two large primes is easy, but factorising their product back into the original primes is computationally infeasible with current technology for sufficiently large inputs (2048+ bits).
GCD, LCM, and the Euclidean Algorithm
The Greatest Common Divisor (GCD) of two numbers is the largest integer that divides both without remainder. The Least Common Multiple (LCM) is the smallest positive integer divisible by both. They are related by: LCM(a,b) = a × b ÷ GCD(a,b). The Euclidean algorithm computes GCD efficiently using repeated division: GCD(48, 18) → GCD(18, 48 mod 18 = 12) → GCD(12, 6) → GCD(6, 0) = 6. This ancient algorithm (Euclid's Elements, ~300 BC) remains one of the most efficient algorithms for its task and is a foundation of modern cryptographic protocols.
Frequently Asked Questions
How do I check if a number is prime?
A prime number is only divisible by 1 and itself. To check, test divisibility by all prime numbers up to the square root of the number. If none divide evenly, the number is prime. For example, to check 97: the square root is about 9.8, so test 2, 3, 5, 7. None divide 97 evenly, so 97 is prime. The Prime Number Checker does this instantly for any integer.
What is prime factorization?
Prime factorization breaks a number into a product of prime numbers. Every integer greater than 1 has a unique prime factorization (Fundamental Theorem of Arithmetic). For example, 360 = 2 x 2 x 2 x 3 x 3 x 5, or written as 2^3 x 3^2 x 5. The Prime Factorization Calculator shows the complete breakdown with exponent notation.
What is the difference between GCD and LCM?
GCD (Greatest Common Divisor) is the largest number that divides both numbers without remainder. LCM (Least Common Multiple) is the smallest number that both numbers divide into evenly. They are related by the formula: GCD(a,b) x LCM(a,b) = a x b. For example, GCD(12,18) = 6 and LCM(12,18) = 36, and 6 x 36 = 12 x 18 = 216.
How does the Euclidean algorithm work?
The Euclidean algorithm finds the GCD by repeated division. Divide the larger number by the smaller, take the remainder, then repeat with the smaller number and the remainder until the remainder is 0. The last non-zero remainder is the GCD. Example: GCD(48,18) = GCD(18,12) = GCD(12,6) = GCD(6,0) = 6. It is one of the oldest and most efficient algorithms known.
What are coprime numbers?
Two numbers are coprime (or relatively prime) if their GCD is 1, meaning they share no common factor other than 1. For example, 8 and 15 are coprime because GCD(8,15) = 1, even though neither is a prime number. Consecutive integers are always coprime. Coprimality is important in cryptography, modular arithmetic, and fraction simplification.