17Prime
- Check
- No divisors in 2..4
Check Prime Number in Java
What you’ll learn
- What makes a number prime (exactly two positive divisors).
- Why checking divisors only up to sqrt(n) is enough.
- Two Java programs: one-number test and prime listing in a range.
- A live preview, edge cases, and optimization notes.
Overview
A prime number is greater than 1 and divisible only by 1 and itself. Instead of checking all numbers up to n-1, we stop at sqrt(n) to keep checks efficient.
Single check
Determine if one value like 17 is prime.
Range listing
Print all primes in a range using the same helper logic.
Fast bound
Stop divisor checks at i * i <= n.
Prerequisites
Loops, modulo operator %, and integer comparisons.
- Prime numbers are integers greater than 1.
- If any divisor exists in
[2, sqrt(n)],nis not prime.
What is a prime number?
A prime number has exactly two positive divisors: 1 and itself. Examples: 2, 3, 5, 7, 11.
Values <= 1 are not prime, and 2 is the only even prime.
Square-root bound
If n = a x b, then at least one of a or b is <= sqrt(n). So checking divisibility only up to sqrt(n) is sufficient.
Result
No divisor up to sqrt(n) means n is prime.
Quick examples
18Not prime
- Check
- Divisible by 2
2Prime
- Special
- Only even prime
Live preview
Runs the same square-root trial-division logic as the Java examples.
Algorithm
Goal: determine whether integer n is prime.
Reject small values
If n <= 1, return false.
Check divisors
Loop i from 2 while i * i <= n.
Return verdict
If any n % i == 0, not prime; otherwise prime.
📜 Pseudocode
Pseudocode
function isPrime(n):
if n <= 1:
return false
for i from 2 while i * i <= n:
if n mod i == 0:
return false
return true1
Check one number
java
public class Main {
static boolean isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int number = 17;
if (isPrime(number)) {
System.out.println(number + " is a prime number.");
} else {
System.out.println(number + " is not a prime number.");
}
}
}2
Prime numbers in range 1 to 20
java
public class Main {
static boolean isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
public static void main(String[] args) {
System.out.println("Prime numbers in the range 1 to 20:");
for (int i = 1; i <= 20; i++) {
if (isPrime(i)) {
System.out.print(i + " ");
}
}
}
}Optimization note
After checking 2, test only odd divisors to reduce constant work.
❓ FAQ
A prime number is an integer greater than 1 that has exactly two positive divisors: 1 and itself.
No. By definition, prime numbers start from 2.
If n has a factor bigger than sqrt(n), the paired factor must be smaller than sqrt(n), so checking up to sqrt(n) is enough.
2 has only two divisors: 1 and 2. It is also the only even prime.
In this tutorial, primality is defined for integers greater than 1, so negatives are not prime.
The square-root trial division check runs in O(sqrt(n)) time and O(1) extra space.
🔄 Input / output examples
| n | Result |
|---|---|
17 | Prime |
18 | Not prime |
1 | Not prime |
Edge cases
n <= 1Values 1, 0, and negatives are not prime.
n = 22 is prime and the only even prime.
⏱️ Time and space complexity
| Method | Time | Extra space |
|---|---|---|
| Single prime check (sqrt bound) | O(√n) | O(1) |
| Check all numbers in range 1..U | about O(U√U) | O(1) |
Summary
- Use trial division up to
sqrt(n). - Time for one check is
O(sqrt(n)).
Did you know?
2 is the only even prime number. 1 is neither prime nor composite.
About the author
9 people found this page helpful