A composite number is an integer n > 1 that has more than two positive divisors — at least one factor other than 1 and n itself. The smallest composite number is 4.
Remember
n is composite ⇔ n > 1 and n is not prime
⇔ n has a divisor d with 1 < d < n
Examples:
4 = 2 × 2 → composite
9 = 3 × 3 → composite
15 = 3 × 5 → composite
7 → prime (not composite)
1 → neither prime nor composite
Four clear steps — then reuse the helper to list composites in a range.
If n <= 1, return False (not composite).
Search for a divisor starting at 2 up to √n.
Stop early when a divisor is found — the number is composite.
If no divisor appears, the number is prime (not composite).
Method
Idea
Time
Best for
√n check
Test divisors from 2 to √n
O(√n)
Interviews, default
Range scan
Reuse the helper over 1 … N
O(N√N)
Listing composites
Pseudocode
Pseudocode
function IsComposite(n):
if n <= 1:
return false
i = 2
while i * i <= n:
if n mod i == 0:
return true // found a factor
i = i + 1
return false // prime
Reference
Cheat Sheet
Keep these facts handy while writing the program.
Topic
Detail
Definition
n > 1 with a factor other than 1 and n
Smallest
4
Not composite
1, primes, and n <= 1
Fast limit
Loop while i * i <= n
1 to 10
4, 6, 8, 9, 10
Classic check
9 → composite; 7 → not
Try it
Live Preview
Enter any integer to see its classification and a factor if it is composite.
Whole numbers (capped at ±999999). Tap a chip or type a value.
Start at 2. As soon as one factor appears, the number is composite.
Calculation
n = 9 (n > 1, so it could be prime or composite)
i = 2 → 9 % 2 != 0 → continue
i = 3 → 9 % 3 == 0 → factor found
9 = 3 × 3
Positive divisors: 1, 3, 9 (three divisors)
Result: composite
Code
Python Programs
Start with an O(√n) check for one number. Then reuse the helper to list composites in a small range.
Example 1 — Check One Number
Look for any divisor from 2 while i * i <= n.
python
def is_composite(n: int) -> bool:
if n <= 1:
return False
i = 2
while i * i <= n:
if n % i == 0:
return True
i += 1
return False
number = 12
if is_composite(number):
print(f"{number} is a composite number.")
else:
print(f"{number} is not a composite number.")
Output
12 is a composite number.
How It Works
Reject n <= 1 immediately — those values are not composite.
Loop while i * i <= n (same as i <= √n, no floating point).
If n % i == 0, a factor exists between 1 and n, so return True.
If the loop finishes with no hit, n is prime, so return False.
For 12, i = 2 divides evenly, so the function reports composite.
Example 2 — Composites from 1 to 10
Reuse the helper and print every composite in a closed range.
python
def is_composite(n: int) -> bool:
if n <= 1:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return True
return False
print("Composite numbers in the range 1 to 10 are:")
composites = [num for num in range(1, 11) if is_composite(num)]
print(" ".join(map(str, composites)))
Output
Composite numbers in the range 1 to 10 are:
4 6 8 9 10
How It Works
Loop from 1 to 10 inclusive.
Call is_composite(num) for each value.
Collect matches in a list comprehension, then print them joined by spaces.
Within 1…10 you should see 4, 6, 8, 9, and 10.
The helper stays pure; the list comprehension only decides what to print.
Edge Cases & Pitfalls
Check these before calling the solution done.
n <= 1
Not composite
Return False before any loop. 1 is neither prime nor composite.
2 and 3
Smallest primes
Both are prime. The loop never finds a factor, so return False.
Squares
Still composite
9, 25, 49 are composite even when the only middle factor repeats.
Negatives
Usually out of scope
Prime/composite talk is for integers greater than 1. Treat negatives as not composite.
Analysis
Time and Space Complexity
Program
Time
Extra space
Single check
O(√n)
O(1)
Range 1…N
O(N√N)
O(1) beyond the answer list
Remember
Key Takeaways
Definition:n > 1 with a factor other than 1 and itself.
Opposite of prime: composite ↔ not prime and n > 1.
Fast check: loop while i * i <= n.
Test set: 4 and 9 true; 1, 2, and 7 false.
One line: if n > 1 and any divisor exists between 2 and √n, the number is composite.
Frequently Asked Questions
An integer greater than 1 that has at least one positive divisor other than 1 and itself. Equivalently, it has more than two positive divisors. The smallest composite number is 4.
Reject n <= 1. Then look for a divisor from 2 through √n. If any divisor is found, the number is composite.
No. The number 1 is neither prime nor composite.
A prime has exactly two positive divisors: 1 and itself. A composite has more than two. Both require n > 1.
Checking divisors up to √n is O(√n) with O(1) extra space. Listing composites in a range of size N costs O(N√N).
