12 Composite
- Factor
2 · 6,3 · 4
Check Composite Number in Java
What you’ll learn
- The correct meaning of composite versus prime and why 1 is neither.
- Trial division to
n/2(classic style) and to√n(interview-leaning optimization). - A range scan like
1–10, a browser live preview, and complexity / edge-case notes.
Overview
A positive integer n > 1 is composite if it has a divisor strictly between 1 and n. This page shows a straightforward loop (up to n/2) for one value, then a √n test reused to print composites in a small interval.
Two programs
Single check with a familiar n/2 bound, then range output with a √n helper.
Live preview
Type an integer and see composite vs not composite (same trial rules as the samples).
Definitions fixed
Some older texts word the definition poorly; this tutorial keeps the Java explanation aligned with standard number theory.
Prerequisites
Integer remainder (%), for loops, and inequalities.
public static void main(String[] args), integer arithmetic, and printing withSystem.out.println.- Optional: why
i * i <= nandi <= n / iare equivalent bounds for positive integers.
What is a composite number?
An integer n > 1 is composite if it is not prime—equivalently, there exists an integer d with 1 < d < n and n % d == 0. Equivalently, n has more than two positive divisors (counting 1 and n).
The integer 1 has only one positive divisor, so it is neither prime nor composite. The number 12 is composite because 2 and 3 (among others) divide it.
Prime exactly two divisors
Composite > two divisors
Unit n = 1
Trial division bound
If n > 1 is composite, write n = d · k with d the smallest divisor greater than 1. Then d is prime and d ≤ k, hence d2 ≤ n and d ≤ ⌊√n⌋.
n = 35gcd(24, 36) = 12. Divisors of 12 are 1, 2, 3, 4, 6, 12—exactly the common divisors printed in the sample output.
Intuition
7 Prime
- Divisors
1and7only
Takeaway: one nontrivial factor is enough to prove composite; proving prime requires no factor up to √n.
Live preview
Enter an integer in the JavaScript safe range. Uses the same “factor in (1, n)” rule: n ≤ 1 is reported as neither composite nor prime in the usual sense.
Algorithm
Goal: decide whether n > 1 has any divisor d with 1 < d < n.
Reject small values
If n ≤ 1, return “not composite” (and not prime in the standard sense).
Trial division
For i from 2 up to ⌊n/2⌋ (loose bound) or while i · i ≤ n (tight bound), if n % i == 0, return composite.
Otherwise prime
If no divisor found, n is prime, hence not composite.
📜 Pseudocode
Pseudocode
function isComposite(n):
if n ≤ 1:
return false
for i from 2 while i * i ≤ n:
if n mod i = 0:
return true
return false1Classic trial up to
Classic trial up to n / 2
Same shape as the original walkthrough: scan i = 2 .. n/2. Correct for all n > 1, though not the tightest upper limit.
java
public class Main {
// Returns true if n is composite, false if n is prime or n <= 1
static boolean isComposite(int number) {
if (number <= 1) {
return false;
}
for (int i = 2; i <= number / 2; i++) {
if (number % i == 0) {
return true;
}
}
return false;
}
public static void main(String[] args) {
int num = 12;
if (isComposite(num)) {
System.out.println(num + " is a composite number.");
} else {
System.out.println(num + " is not a composite number.");
}
}
}Explanation
Any nontrivial factor of n is at most n/2 when n ≥ 4, so the loop bound is safe. Smaller n are covered by the early loop range and the n ≤ 1 guard.
if (number <= 1)Edge guard. 0 and 1 are not composite (and not prime).
2
√n test and composites from 1 to 10
Uses integer i <= n / i instead of Math.sqrt to avoid floating point. Prints the same line as the reference range demo: 4 6 8 9 10.
java
public class Main {
// true = composite, false = prime or n <= 1
static boolean isCompositeSqrt(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
return true;
}
}
return false;
}
public static void main(String[] args) {
System.out.println("Composite numbers in the range 1 to 10 are:");
for (int i = 1; i <= 10; i++) {
if (isCompositeSqrt(i)) {
System.out.print(i + " ");
}
}
System.out.println();
}
}Explanation
The condition i <= n / i is equivalent to i * i ≤ n for positive integers without calling Math.sqrt.
return false;Prime branch. No divisor found in [2, √n], so n is prime and not composite.
Optimization
√ bound. Prefer i <= n / i over n/2 for large n.
Primes first. Testing only prime i (sieve or wheel) wins more but adds setup; rarely required for a one-off interview check.
Interview: define composite precisely, handle n ≤ 1, then cite the √ trial bound.
❓ FAQ
A composite number is an integer n strictly greater than 1 that is not prime: equivalently, n has a divisor d with 1 < d < n, or n has more than two positive divisors. Examples: 4, 6, 8, 9, 10.
No. By standard definition, 1 is a unit, not prime and not composite.
No. Two is prime; it has no divisor strictly between 1 and 2.
If n has a nontrivial divisor d, then n = d·k with d ≤ k, so d ≤ √n. Any composite n therefore has a divisor in [2, ⌊√n⌋]. Scanning up to n/2 is correct but looser; √n is the usual interview optimization.
Primality and compositeness are defined for integers greater than 1. Negative integers and 0 are classified separately; most simple Java demos assume a nonnegative or positive input.
Checking one n with trial up to √n is O(√n) time and O(1) extra space. Scanning every integer in [a,b] multiplies that cost.
🔄 Input / output examples
Change num in Example 1 or the loop bounds in Example 2 to experiment.
| n | Composite? | Note |
|---|---|---|
12 | Yes | Divisible by 2, 3, … |
7 | No | Prime |
1 | No | Neither prime nor composite |
4 | Yes | Smallest composite |
Edge cases and pitfalls
Loose wording about “excluding 1 and itself” often confuses beginners; the code paths below stay consistent with standard definitions.
n = 2
Smallest prime
The loop never finds a divisor; the function must return not composite. Do not label 2 as composite.
n = 1
Neither class
Printing “not composite” is true but does not mean “prime”—phrase the console or UI message carefully if you need both concepts.
Squares
i * i == n
Perfect squares such as 9 are composite; the √ loop catches factor 3 when 3 * 3 == 9.
Overflow
i * i <= n
Squaring i in a wide loop can overflow int; using i <= n / i avoids i * i for n > 0.
⏱️ Time and space complexity
| Method | Time (single n) | Extra space |
|---|---|---|
Trial to n/2 | O(n) | O(1) |
Trial to √n (i <= n / i) | O(√n) | O(1) |
Range [a, b] | O((b-a+1)√b) with √ test per value | O(1) |
Space excludes the printed sequence itself; only a handful of integer locals are needed.
Summary
- Definition: composite means
n > 1and not prime;1is neither. - Code: trial division; tighten the loop with
i <= n / i. - Watch-outs: wording in old tutorials,
n = 2, and overflow oni * i.
Did you know?
The integer 1 is neither prime nor composite. The smallest composite is 4 (2 × 2). Every composite n has a prime divisor p with p ≤ √n, which is why trial division only needs to reach √n.
About the author
8 people found this page helpful