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 pick a basic or O(√n) loop.
If n <= 1, return false (not composite).
Search for a divisor starting at 2.
Stop early when a divisor is found — the number is composite.
If no divisor appears before the limit, the number is prime (not composite).
Method
Idea
Time
Best for
Basic loop
Test divisors from 2 to n / 2
O(n)
Interviews, small n
√n check
Test divisors from 2 to √n
O(√n)
Larger n, optimizations
Pseudocode
Pseudocode
function IsComposite(n):
if n <= 1:
return false
for i from 2 to floor(n / 2):
if n mod i == 0:
return true // found a factor
return false // prime (or 2, 3, …)
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
Basic limit
Loop 2 … n / 2
Fast limit
Loop 2 … √n
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
C# Programs
Start with the readable loop to n / 2. Then stop at √n for the usual interview optimization.
Example 1 — Check One Number
Look for any divisor from 2 through n / 2.
C#
using System;
class Program
{
static bool IsComposite(int n)
{
if (n <= 1)
{
return false;
}
for (int i = 2; i <= n / 2; i++)
{
if (n % i == 0)
{
return true;
}
}
return false;
}
static void Main()
{
int number = 9;
if (IsComposite(number))
{
Console.WriteLine(number + " is a composite number.");
}
else
{
Console.WriteLine(number + " is not a composite number.");
}
}
}
Output
9 is a composite number.
How It Works
Reject n <= 1 immediately — those values are not composite.
Loop i from 2 to n / 2. No proper factor can be larger than n / 2.
If n % i == 0, a factor exists between 1 and n, so return true.
If the loop finishes with no hit, n is prime (or 2/3), so return false.
For 9, i = 3 divides evenly, so the method reports composite.
Example 2 — O(√n) Check
Any factor larger than √n pairs with a smaller one, so stopping at √n is enough.
C#
using System;
class Program
{
static bool IsCompositeFast(int n)
{
if (n <= 1)
{
return false;
}
for (int i = 2; i <= n / i; i++)
{
if (n % i == 0)
{
return true;
}
}
return false;
}
static void Main()
{
Console.WriteLine(IsCompositeFast(9)); // True (composite)
Console.WriteLine(IsCompositeFast(7)); // False (prime)
Console.WriteLine(IsCompositeFast(1)); // False (neither)
}
}
Output
True
False
False
How It Works
Same early exit for n <= 1.
The condition i <= n / i means i <= √n without floating point, and it avoids overflow.
If a small factor i exists, its partner n / i is at least as large as i — so finding either proves composite.
No factor up to √n means n is prime, so return false.
Checks: 9 is composite, 7 is prime, 1 is neither.
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
Basic loop to n/2
O(n)
O(1)
Loop up to √n
O(√n)
O(1)
Remember
Key Takeaways
Definition:n > 1 with a factor other than 1 and itself.
Opposite of prime: composite ↔ not prime and n > 1.
Two loops: basic 2 … n/2, or optimized 2 … √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/2 (simple) or through √n (optimized). 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.
The basic loop is O(n). Checking divisors only up to √n is O(√n). Both use O(1) extra space.
