12 Composite
- Factor
2 * 6,3 * 4
Check Composite Number in Python
What you’ll learn
- How to classify a number as composite correctly.
- How to test using trial division with sqrt optimization.
- How to print composite numbers in a range.
Overview
A positive integer n > 1 is composite if it has a divisor strictly between 1 and n. This page shows a direct check for one value and an optimized √n check for range output.
Two programs
Single-number check and range output from 1 to 10 with clean Python functions.
Live preview
Type an integer and classify it instantly using the same divisor logic as the examples.
Interview clarity
Get the exact definition right: 1 is neither prime nor composite, and one nontrivial divisor proves compositeness.
Prerequisites
Python basics: loops, modulo operator, and integer comparisons.
for,while,if, and function definitions in Python.- Using integer arithmetic (
%,**) and formatting output withprint().
What is a composite number?
An integer n > 1 is composite if there exists a divisor d such that 1 < d < n and n % d == 0. Equivalently, n has more than two positive divisors.
1 is neither prime nor composite. Example: 12 is composite because both 2 and 3 divide it exactly.
Prime exactly two divisors
Composite > two divisors
Unit n = 1
Trial division bound
If n is composite, there is a factor pair n = a * b. At least one of a or b must be less than or equal to √n, so checking divisors only up to √n is enough.
n = 35Try i = 2..5. Once 5 divides 35, the number is proven composite.
Intuition
7 Prime
- Divisors
1and7only
Takeaway: finding any nontrivial divisor is enough to mark a number composite.
Live preview
Enter an integer to check whether it is composite.
Algorithm
Handle n <= 1
Not composite.
Try divisors
Loop i from 2 while i*i <= n.
If divisible
If n % i == 0, n is composite.
📜 Pseudocode
Pseudocode
function is_composite(n):
if n <= 1:
return false
i = 2
while i * i <= n:
if n % i == 0:
return true
i = i + 1
return false1
Check one number
Simple and interview-friendly: short function, fast early return, and integer-safe loop bound.
python
def is_composite(number: int) -> bool:
if number <= 1:
return False
i = 2
while i * i <= number:
if number % i == 0:
return True
i += 1
return False
n = 12
if is_composite(n):
print(f"{n} is a composite number.")
else:
print(f"{n} is not a composite number.")Explanation
The loop stops at i * i <= number because any factor above √n has a matching factor below √n.
2
Composite numbers from 1 to 10
Reuses the helper function and prints only values that satisfy the composite test.
python
def is_composite(number: int) -> bool:
if number <= 1:
return False
for i in range(2, int(number ** 0.5) + 1):
if number % i == 0:
return True
return False
print("Composite numbers in the range 1 to 10 are:")
for num in range(1, 11):
if is_composite(num):
print(num, end=" ")Optimization
Use √n bound. Keep the loop as while i * i <= n or for i in range(2, int(n ** 0.5) + 1).
Early exit. Return immediately on first divisor for best average runtime.
Interview: define composite correctly, mention why √n is sufficient, and handle n <= 1.
🔄 Input / output examples
Try these values in the first program or live preview box.
| n | Composite? | Note |
|---|---|---|
12 | Yes | Divisible by 2 and 3 |
7 | No | Prime |
1 | No | Neither prime nor composite |
4 | Yes | Smallest composite |
❓ FAQ
A composite number is an integer greater than 1 that has at least one divisor other than 1 and itself.
No. The number 1 is neither prime nor composite.
If n has a factor larger than sqrt(n), it must also have a paired factor smaller than sqrt(n).
No. 2 is prime because its only positive divisors are 1 and 2.
Composite/prime classification is usually defined for integers greater than 1 only.
The optimized check runs in O(sqrt(n)) time and O(1) extra space.
Edge cases and pitfalls
1
Neither prime nor composite
Do not mark 1 as prime/composite.
2, 3
Prime small values
Both are not composite.
Negative
Out of definition
Composite classification is for integers greater than 1.
⏱️ Time and space complexity
| Method | Time | Extra space |
|---|---|---|
| Trial division to n/2 | O(n) | O(1) |
| Trial division to sqrt(n) | O(sqrt(n)) | O(1) |
Summary
- Definition: n > 1 and non-prime means composite.
- Best check: test divisors only up to sqrt(n).
- Remember: 1 is neither prime nor composite.
Did you know?
The number 1 is neither prime nor composite. The smallest composite number is 4.
About the author
8 people found this page helpful