Prime Number Checker
Check if a number is prime or composite instantly. Get factors, prime factorization, trial-division details, and neighboring prime numbers with this free online prime checker.
Prime Number Checker
| Step | Verification Description |
|---|---|
| 1 | Calculated √97 ≈ 9.85. Candidate prime divisors ≤ 9. |
| 2 | Tested prime candidate divisors up to 9. No divisor divides 97 evenly. |
| 3 | 97 has exactly two distinct positive divisors: 1 and 97. Therefore, 97 is Prime. |
Overview
The ToolMono Prime Number Checker is an enterprise-grade primality testing suite engineered for software developers, cryptographers, mathematics educators, and students. It evaluates integer primality instantly using 100% client-side BigInt arbitrary-precision math.
Equipped with automatic algorithm selection (switching between Trial Division O(√N) and the Miller-Rabin Primality Test), prime factorization trees, complete divisor lists, adjacent prime lookup (previous/next prime), range generation, and batch mode, ToolMono provides the definitive reference platform for primality testing. Explore companion tools: GCD & LCM Calculator, Online Calculator, Scientific Calculator, Binary ↔ Decimal Converter, Decimal ↔ Hex Converter, and Decimal ↔ Octal Converter.
How to Use
Type any positive integer (e.g. 97, 91, or a large BigInt) into the input box.
View immediate classification (Prime vs Composite) and trial division proof steps.
For composite numbers, inspect factor pairs (e.g. 7 × 13), prime factorization exponent forms (e.g. 2³ × 3² × 5), and complete divisor lists.
Use 1-click buttons to navigate to the Previous Prime or Next Prime, or switch to Batch / Range Generator mode.
How to Check if a Number Is Prime Manually
To determine whether an integer is prime by hand without advanced software, follow this 4-step procedure:
- Confirm the target number N is a positive integer greater than 1.
- Calculate the square root of the number (√N).
- List all prime numbers less than or equal to ⌊√N⌋.
- Test divisibility of N by each candidate prime. If any prime divides N with remainder 0, N is composite. If no prime divides N evenly, N is prime.
How the Primality Test Works (Trial Division Algorithm)
The fundamental algorithm used for deterministic primality verification is Trial Division.
- Check if N ≤ 1. If so, classify N as neither prime nor composite.
- Handle N = 2 and N = 3 as special prime cases.
- Check if N is even (N % 2 = 0) or divisible by 3 (N % 3 = 0). If yes, N is composite.
- Calculate ⌊√N⌋ to establish the upper bound for candidate testing.
- Test odd candidates of the form 6k ± 1 up to √N.
- If any candidate divides N, record the smallest factor and mark N as composite. If no candidate divides N, mark N as prime.
Why You Only Need to Check Divisors Up to √N
A major performance optimization in primality testing is limiting candidate factor checks to √N. Here is the mathematical proof:
Suppose N is a composite number that can be factored into two positive integers:
If both a > √N and b > √N, then multiplying them together would yield:
This contradicts our initial statement that a × b = N. Therefore, at least one factor must be less than or equal to √N (a ≤ √N or b ≤ √N).
If no factor is found up to √N, it is mathematically impossible for any larger factor pair to exist.
Worked Example: Is 91 Prime?
The number 91 is a classic composite number that often tricks students into believing it is prime. Let's run the primality test:
Prime vs. Composite Numbers
| Classification | Divisor Definition | Example Numbers |
|---|---|---|
| Prime Number | Exactly two distinct positive divisors (1 and itself) | 2, 3, 5, 7, 11, 13, 17, 19, 97 |
| Composite Number | More than two positive divisors (at least one prime factor ≤ √N) | 4, 6, 8, 9, 10, 12, 14, 15, 91, 360 |
| Neither Prime nor Composite | 0, 1, or negative integers (do not meet 2-divisor definition) | -7, -1, 0, 1 |
Prime Checker Edge Cases
| Input Number | Status Result | Mathematical Explanation |
|---|---|---|
| -5 | Neither | Negative integers are not prime. Primality is defined for positive integers > 1. |
| 0 | Neither | 0 is divisible by all non-zero integers and has infinite divisors. |
| 1 | Neither | 1 has only one positive divisor (1). A prime must have exactly two distinct divisors. |
| 2 | Prime | The smallest prime number and the only even prime number. |
| 3 | Prime | Exactly two distinct positive divisors: 1 and 3. |
| 4 | Composite | Divisible by 1, 2, and 4 (2 × 2). |
| 97 | Prime | No prime candidate ≤ √97 (9.85) divides 97. |
Common Prime Number Examples
| Number | Classification | Reason & Divisors |
|---|---|---|
| 2 | Prime | Only divisible by 1 and 2 |
| 3 | Prime | Only divisible by 1 and 3 |
| 4 | Composite | Divisible by 2 (2 × 2) |
| 5 | Prime | Only divisible by 1 and 5 |
| 9 | Composite | Divisible by 3 (3 × 3) |
| 11 | Prime | Only divisible by 1 and 11 |
| 15 | Composite | Divisible by 3 and 5 (3 × 5) |
| 17 | Prime | Only divisible by 1 and 17 |
| 25 | Composite | Divisible by 5 (5 × 5) |
| 97 | Prime | No prime candidate ≤ √97 (2, 3, 5, 7) divides 97 |
Important Properties of Prime Numbers
- The Only Even Prime: 2 is the smallest prime and the only even prime number. All other even numbers are composite.
- Fundamental Theorem of Arithmetic: Every integer greater than 1 is either prime itself or can be uniquely factored into a product of primes.
- Infinitude of Primes (Euclid's Theorem): There are infinitely many prime numbers, proven by Euclid around 300 BCE.
- Prime Divisor Guarantee: Every composite integer N has at least one prime factor p ≤ √N.
Algorithms: Trial Division vs. Miller-Rabin
ToolMono automatically selects the optimal primality test based on the size of the input number:
Used for small numbers (N ≤ 10^7). It checks divisibility by 2, 3, and odd numbers of the form 6k ± 1 up to ⌊√N⌋. Guaranteed 100% deterministic accuracy.
Used for large BigInt numbers (N > 10^7). Expresses N - 1 = 2^s · d and tests 12 deterministic/probabilistic bases. Operates in O(k log³ N) time for cryptographic efficiency.
How Is Prime Testing Done for Very Large Numbers?
While trial division up to √N works quickly for everyday numbers, testing 256-bit or 1024-bit cryptographic integers would take millions of years with trial division.
For large BigInt integers, algorithms like the Miller–Rabin Primality Test evaluate modular witness equations (a^d ≡ 1 mod N). By checking multiple independent witness bases, primality can be confirmed with deterministic certainty up to 2^64 and probabilistic certainty (1 - 4^-k) for arbitrary-precision BigInts.
Prime Factorization & Exponent Notation
According to the Fundamental Theorem of Arithmetic, every positive integer greater than 1 can be uniquely represented as a product of prime numbers.
360 ÷ 2 = 180
180 ÷ 2 = 90
90 ÷ 2 = 45
45 ÷ 3 = 15
15 ÷ 3 = 5
5 ÷ 5 = 1
Divisors & Divisibility Rules
| Divisor | Divisibility Rule | Example |
|---|---|---|
| 2 | Last digit is even (0, 2, 4, 6, 8) | 128 (Ends in 8) |
| 3 | Sum of digits is divisible by 3 | 123 (1+2+3 = 6) |
| 5 | Last digit is 0 or 5 | 365 (Ends in 5) |
| 11 | Alternating sum of digits is divisible by 11 | 121 (1 - 2 + 1 = 0) |
Prime Range Generator
Generate all prime numbers between lower bound A and upper bound B instantly. Ideal for generating test vectors for algorithm development.
Programming Code Examples
Reference code snippets for Trial Division and Prime Factorization across major programming languages:
function isPrime(n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 === 0 || n % 3 === 0) return false;
for (let i = 5; i * i <= n; i += 6) {
if (n % i === 0 || n % (i + 2) === 0) return false;
}
return true;
}function factorize(n) {
const factors = [];
let d = 2;
while (n >= 2) {
if (n % d === 0) { factors.push(d); n /= d; }
else { d++; }
}
return factors;
}def is_prime(n):
if n <= 1: return False
if n <= 3: return True
if n % 2 == 0 or n % 3 == 0: return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0: return False
i += 6
return Truedef prime_factors(n):
i = 2
factors = []
while i * i <= n:
if n % i:
i += 1
else:
n //= i
factors.append(i)
if n > 1:
factors.append(n)
return factorspublic static boolean isPrime(long n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (long i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}// Prime Factorization in Java
public static List<Long> primeFactors(long n) {
List<Long> factors = new ArrayList<>();
for (long i = 2; i * i <= n; i++) {
while (n % i == 0) { factors.add(i); n /= i; }
}
if (n > 1) factors.add(n);
return factors;
}package main
func IsPrime(n int64) bool {
if n <= 1 { return false }
if n <= 3 { return true }
if n%2 == 0 || n%3 == 0 { return false }
for i := int64(5); i*i <= n; i += 6 {
if n%i == 0 || n%(i+2) == 0 { return false }
}
return true
}// Go Factorization
func PrimeFactors(n int64) []int64 {
factors := []int64{}
for i := int64(2); i*i <= n; i++ {
for n%i == 0 { factors = append(factors, i); n /= i }
}
if n > 1 { factors = append(factors, n) }
return factors
}#include <stdbool.h>
bool isPrime(long long n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (long long i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}// C++ Vector Factorization
#include <vector>
std::vector<long long> primeFactors(long long n) {
std::vector<long long> factors;
for (long long i = 2; i * i <= n; i++) {
while (n % i == 0) { factors.push_back(i); n /= i; }
}
if (n > 1) factors.push_back(n);
return factors;
}fn is_prime(n: u64) -> bool {
if n <= 1 { return false; }
if n <= 3 { return true; }
if n % 2 == 0 || n % 3 == 0 { return false; }
let mut i = 5;
while i * i <= n {
if n % i == 0 || n % (i + 2) == 0 { return false; }
i += 6;
}
true
}fn prime_factors(mut n: u64) -> Vec<u64> {
let mut factors = Vec::new();
let mut i = 2;
while i * i <= n {
while n % i == 0 { factors.push(i); n /= i; }
i += 1;
}
if n > 1 { factors.push(n); }
factors
}public static bool IsPrime(long n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (long i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}public static List<long> PrimeFactors(long n) {
var factors = new List<long>();
for (long i = 2; i * i <= n; i++) {
while (n % i == 0) { factors.Add(i); n /= i; }
}
if (n > 1) factors.Add(n);
return factors;
}function isPrime($n) {
if ($n <= 1) return false;
if ($n <= 3) return true;
if ($n % 2 == 0 || $n % 3 == 0) return false;
for ($i = 5; $i * $i <= $n; $i += 6) {
if ($n % $i == 0 || $n % ($i + 2) == 0) return false;
}
return true;
}function primeFactors($n) {
$factors = [];
for ($i = 2; $i * $i <= $n; $i++) {
while ($n % $i == 0) { $factors[] = $i; $n /= $i; }
}
if ($n > 1) $factors[] = $n;
return $factors;
}func isPrime(_ n: Int) -> Bool {
if n <= 1 { return false }
if n <= 3 { return true }
if n % 2 == 0 || n % 3 == 0 { return false }
var i = 5
while i * i <= n {
if n % i == 0 || n % (i + 2) == 0 { return false }
i += 6
}
return true
}func primeFactors(_ n: Int) -> [Int] {
var num = n, factors = [Int](), i = 2
while i * i <= num {
while num % i == 0 { factors.append(i); num /= i }
i += 1
}
if num > 1 { factors.append(num) }
return factors
}fun isPrime(n: Long): Boolean {
if (n <= 1L) return false
if (n <= 3L) return true
if (n % 2L == 0L || n % 3L == 0L) return false
var i = 5L
while (i * i <= n) {
if (n % i == 0L) return false
i += 6L
}
return true
}fun primeFactors(n: Long): List<Long> {
var num = n; val factors = mutableListOf<Long>()
var i = 2L
while (i * i <= num) {
while (num % i == 0L) { factors.add(i); num /= i }
i++
}
if (num > 1L) factors.add(num)
return factors
}Developer & Low-Level Computer Guide
Prime numbers are foundational to public-key cryptography (such as RSA), Diffie-Hellman key exchange, hashing algorithms, and pseudo-random number generators.
First 100 Prime Numbers & Mersenne Primes
AI Overview Answers
A Prime Number Checker is a mathematical tool that verifies whether a given integer is prime (divisible only by 1 and itself) or composite (divisible by additional prime factors).
Frequently Asked Questions
References & Standards
NIST Digital Library of Mathematical Functions: Prime Numbers
NIST reference repository for primality testing algorithms.
ISO 80000-2: Mathematics Notation Standard
International ISO standard for integer arithmetic and divisibility.
ECMAScript BigInt Specification
Official specification for arbitrary-precision integer primality testing.
Related Tools
Browse all toolsGCD and LCM Calculator
Calculate the GCD (GCF/HCF) and LCM of two or more numbers instantly. See step-by-step Euclidean algorithm and prime factorization methods with accurate results.
Online Calculator
Use ToolMono's free online calculator for quick everyday math, expressions, percentages, powers, roots, and parentheses. Includes calculation history and keyboard support.
Scientific Calculator
Use ToolMono's free Scientific Calculator for advanced mathematical calculations. Supports trigonometric, inverse, hyperbolic, logarithmic, exponential, factorial, scientific notation, degree/radian modes, calculation history, and 100% client-side processing.
Binary ↔ Decimal Converter
Free online Binary Decimal Converter. Convert binary base-2 to decimal base-10 instantly. Supports BigInt, two's complement, 8–256 bit signed, and step breakdown.
Decimal ↔ Hex Converter
Free online Decimal to Hex Converter. Convert base-10 to base-16 hexadecimal instantly. Supports BigInt, two's complement, 8–64 bit signed/unsigned, and live steps.
Decimal to Octal Converter
Free online Decimal to Octal converter with instant step-by-step division steps. Convert Base-10 to Base-8 and Octal to Decimal accurately in your browser.