Definition
n > 1
Composite means there exists d with 1 < d < n and n % d == 0.
Check Composite Number in PHP
Overview
What You’ll Learn
A composite number is an integer greater than 1 with a nontrivial divisor. This tutorial covers the definition vs prime, a live preview, algorithm steps, worked PHP examples, edge cases, and complexity.
vs Prime
Divisor count
Prime: exactly two divisors. Composite: more than two. 1: neither.
√n Bound
Trial division
Any factor pair has one factor ≤ √n — stop the loop there.
Early Exit
First hit
Return true as soon as any nontrivial divisor is found.
Live Preview
Try any n
Classify a number as composite, prime, or neither instantly.
O(√n)
Complexity
Optimized check uses O(√n) time and O(1) extra space.
Introduction
Composite numbers are integers n > 1 that are not prime — they have at least one divisor strictly between 1 and n. Classic examples: 4, 6, 8, 9, 10, 12.
The number 1 is neither prime nor composite. Finding any nontrivial divisor is enough to prove compositeness; you do not need to list every factor.
Why it matters?
It drills the prime/composite distinction, trial division, and the √n optimization interviewers expect.
Key Highlights
Nontrivial Factor
One divisor in (1, n) proves composite.
1 Is Special
Neither prime nor composite — always handle n ≤ 1.
√n Is Enough
Factor pairs guarantee a small factor ≤ √n.
Smallest Is 4
4 = 2 × 2 is the first composite.
In short: if n > 1 and any i from 2…√n divides n, then n is composite; otherwise (for n > 1) it is prime.
Foundation
📝 Problem & Approach
Given an integer n, decide whether it is composite. Optionally list composites in a range.
php
# 12 → divisible by 2 → composite
# 7 → no divisor in 2..√7 → not composite (prime)
# 1 → neitherInputs & Outputs
| Item | Type | Description |
|---|---|---|
n | int | Integer to classify (composite defined for n > 1). |
| Return / print | bool / text | true if composite; otherwise not (prime or neither). |
Minimal workflow
Pseudocode
function isComposite(n):
if n <= 1:
return false
i = 2
while i * i <= n:
if n % i == 0:
return true
i = i + 1
return falseMethod comparison
| Method | Idea | Notes |
|---|---|---|
| Trial to n/2 | Check every i up to n/2 | Simple but O(n) |
| Trial to √n | Loop while $i <= intdiv($n, $i) | Standard interview check |
| Show a factor | Return first divisor found | Great for explaining why |
Cheat Sheet
⚡ Quick Reference
| Goal | Pattern |
|---|---|
| Guard n ≤ 1 | if ($n <= 1) return false |
| √n loop | for ($i = 2; $i <= intdiv($n, $i); $i++) |
| Divisor hit | if ($n % $i === 0) return true |
| Range filter | if (isCompositeSqrt($i)) echo $i |
| Smallest composite | 4 |
| Neither case | 1 (and usually n ≤ 1) |
Compare
📋 Prime vs Composite vs Neither
Three mutually exclusive buckets for positive integers.
Prime
2 divisorsOnly 1 and itself — e.g. 2, 3, 5, 7
Composite
> 2 divisorsHas a nontrivial factor — e.g. 4, 6, 9, 12
Neither
n = 1Unit — not prime, not composite
Interview tip
handle n<=1Say the definition before coding the loop
Context
When This Problem Shows Up
Reach for composite checks when classifying integers next to primes.
Interview warm-ups
Tests definition accuracy and √n trial division.
Teaching number types
Pairs naturally with the prime-number lesson.
Range / filter tasks
Print all composites in 1…N for small N.
Gateway to factorization
Once composite, the next question is often “find a factor.”
Not for floats / negatives
Standard definition applies to integers greater than 1.
Key benefit: one short boolean check that forces precise definitions and the classic √n optimization.
Interactive
🔮 Live Preview
Enter an integer to check whether it is composite.
Hands-On
Examples Gallery
Three complete PHP programs — single-number check, range listing, and a factor-proof helper. Click View Output to reveal sample console results.
📚 Getting Started
Boolean check with √n trial division.
Example 1 — Check One Number
Short function, fast early return, and integer-safe loop bound.
php
<?php
function isCompositeSqrt(int $n): bool
{
if ($n <= 1) return false;
for ($i = 2; $i <= intdiv($n, $i); $i++) {
if ($n % $i === 0) return true;
}
return false;
}
$num = 12;
echo isCompositeSqrt($num)
? "$num is a composite number."
: "$num is not a composite number.";
?>How It Works
Values ≤ 1 return false immediately. The loop stops at $i <= intdiv($n, $i) (same as $i * $i <= $n) because any factor above √n has a matching factor below √n.
⚡ Range Output
Reuse the helper to filter a small interval.
Example 2 — Composite Numbers from 1 to 10
Print only values that satisfy the composite test.
php
<?php
function isCompositeSqrt(int $n): bool
{
if ($n <= 1) return false;
for ($i = 2; $i <= intdiv($n, $i); $i++) {
if ($n % $i === 0) return true;
}
return false;
}
echo "Composite numbers in the range 1 to 10 are:\n";
for ($i = 1; $i <= 10; $i++) {
if (isCompositeSqrt($i)) echo $i . " ";
}
?>How It Works
Same √n test using the integer-safe bound $i <= intdiv($n, $i). From 1 to 10 the composites are exactly 4, 6, 8, 9, 10.
🔎 Prove It
Return the first nontrivial factor for explanations.
Example 3 — Find a Witness Factor
If composite, report one divisor that proves it.
php
<?php
function firstFactor(int $n): ?int
{
if ($n <= 1) return null;
for ($i = 2; $i <= intdiv($n, $i); $i++) {
if ($n % $i === 0) return $i;
}
return null;
}
foreach ([12, 7, 1, 9] as $n) {
$f = firstFactor($n);
if ($f === null) {
$label = ($n <= 1) ? "neither" : "prime";
echo "$n: not composite ($label)\n";
} else {
echo "$n: composite (divisible by $f)\n";
}
}
?>How It Works
Same loop as isCompositeSqrt, but returns the divisor instead of a boolean. Handy in interviews when the follow-up is “show me a factor.”
🧠 How the Algorithm Decides
1
Guard n ≤ 1
Not composite (neither prime nor composite).
Guard
2
Try divisors
Loop $i from 2 while $i <= intdiv($n, $i).
Scan
3
If divisible
If n % i == 0, return true — proven composite.
Hit
=
Result
No divisor found → not composite (for n > 1 that means prime).
Trace
🔎 Worked Walkthrough — n = 35
Trace trial division up to √35 ≈ 5.9.
| i | i * i ≤ 35? | 35 % i | Action |
|---|---|---|---|
2 | Yes | 1 | Continue |
3 | Yes | 2 | Continue |
4 | Yes | 3 | Continue |
5 | Yes | 0 | Return composite |
Final: 35 is composite (divisible by 5; 35 = 5 × 7).
Use Cases
Where composite checks show up beyond the interview prompt.
1. Interview Warm-Ups
Definition + √n loop in one tight problem.
Example: write isCompositeSqrt($n).
2. Teaching Prime Contrast
Makes “more than two divisors” concrete.
Example: chalkboard 12 vs 7.
3. Range Filters
List composites in a classroom range.
Example: 1 to 10 → 4 6 8 9 10.
4. Factorization Gateway
Once composite, find prime factors next.
Example: Smith-number pipelines.
5. Complexity Practice
Argue why √n beats scanning to n/2.
Example: “why stop at sqrt?”
6. Edge-Case Discipline
Forces handling of 1, 2, and negatives.
Example: classify 1 correctly.
Pro Tip: say “composite = n > 1 and not prime” before coding — then implement the divisor search.
Advantages
Why this pattern works well in interviews and classwork.
1. Clear Definition
One nontrivial divisor is enough — no full factor list required.
2. √n Optimization
Same bound used in prime checks — transferable skill.
3. Tiny Extra Memory
A few integers suffice — O(1) extra space.
4. Early Exit
Even composites like 12 return after the first divisor.
Pro Tip: prefer $i <= intdiv($n, $i) (or $i * $i <= $n) over float sqrt when interviewers care about integer precision.
Usage Tips
Small habits that keep composite checks interview-ready.
1. Define Before Coding
State n > 1 with a nontrivial divisor, and that 1 is neither.
2. Use the √n Bound
Explain why scanning past √n is unnecessary.
3. Return on First Hit
Do not keep looping after finding a divisor.
4. Spot-Check Classics
Assert 4, 9, 12 are composite and 2, 3, 7 are not.
5. Mention Negatives
Say the definition is for integers > 1 only.
Pro Tip: if asked for a proof, return the first factor — same loop, better storytelling.
Common Pitfalls
Mistakes that commonly break composite-number solutions.
1. Calling 1 Composite
1 has only one positive divisor.
→ Return false / “neither” for n ≤ 1.
2. Marking 2 or 3 Composite
Both are prime.
→ The √n loop finds no divisor for them.
3. Scanning All the Way to n
Wasteful and signals weak number sense.
→ Stop at √n (or i * i ≤ n).
4. Off-by-One on the Bound
Using float
sqrt($n)and casting can miss a factor near perfect squares.→ Prefer
$i <= intdiv($n, $i).5. Treating Negatives as Composite
Standard school definition uses integers > 1.
→ Reject or document negatives explicitly.
Edge Cases
Check these inputs before calling the solution done.
1
Neither prime nor composite
Do not mark 1 as prime or composite.
2, 3
Prime small values
Both are not composite.
4
Smallest composite
4 = 2 × 2 — first positive composite.
Negative
Out of definition
Composite classification is for integers greater than 1.
Perfect square
9, 25, 49
Still composite if > 1 (except 1 itself).
Large n
√n still fine
Use integer i * i <= n to avoid float drift.
Math
⚖️ Facts Worth Knowing
Handy follow-ups interviewers sometimes ask.
- Partition. Every integer > 1 is either prime or composite — never both.
- Even composites. Every even n > 2 is composite (divisible by 2).
- Factor pair. If n = a × b with a ≤ b, then a ≤ √n.
- Smallest. 4 is the smallest composite; 9 is the smallest odd composite.
Drill
🎯 Practice Problems
Try these variations to lock in the pattern.
1. Verify classics
- 4, 6, 9, 12 → composite
- 2, 3, 5, 7 → not
- 1 → neither
2. Range 1 to 20
- List all composites
- Compare with primes in the same range
3. Witness factor
- Return the first divisor found
- Print n = f × (n // f)
4. Flip to is_prime
- Implement prime using the same loop
- Assert not both for n > 1
Important
Notes
- Definition: n > 1 with a divisor strictly between 1 and n.
- Best check: test divisors only up to √n and exit early.
- Remember: 1 is neither prime nor composite.
- State O(√n) time and O(1) extra space.
Quick Takeaway: for n > 1, any divisor in 2…√n proves composite; otherwise the number is prime.
Analysis
⏱️ Time and Space Complexity
| Method | Time | Extra space |
|---|---|---|
| Trial division to n/2 | O(n) | O(1) |
| Trial division to √n | O(√n) | O(1) |
| Range 1…N with √n check | O(N √N) | O(1) |
🎉 Conclusion
Composite numbers are integers greater than 1 with a nontrivial divisor. Guard n ≤ 1, scan up to √n, and return early on the first hit.
Practice the three examples above, then continue to Smith numbers for a composite-number follow-up that uses prime factors and digit sums.
Always handle 1 correctly, explain the √n bound, and state O(√n) time.
Pro Tips
💡 Best Practices
✅ Do
- Define composite before coding
- Handle n ≤ 1 explicitly
- Use i * i ≤ n for the bound
- Return on the first divisor
- Test 1, 2, 4, and 9
❌ Don’t
- Call 1 composite
- Call 2 or 3 composite
- Scan all the way to n
- Ignore negatives in the definition
- Skip explaining √n
Summary
Key Takeaways
Knowledge Unlocked
Five things to remember about composite numbers
Classify integers the interview-friendly way.
5
Core concepts 01
Rule
n > 1 + factor
Definition 02
Neither
1 is special
Guard 03
Bound
Scan to √n
Math 04
Exit
First divisor
Code 05
Complexity
O(√n) time
Analysis❓ Frequently Asked Questions
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.
Prime numbers have exactly two positive divisors (1 and themselves). Composite numbers have more than two.
4 — because 4 = 2 * 2 and it is greater than 1.
Did you Know? 🔊
The number 1 is neither prime nor composite; the smallest composite number is 4.
Continue to Smith Number
Learn how some composites have digit sums equal to the digit sums of their prime factors.
About the author
9 people found this page helpful