A composite number is an integer greater than 1 that has at least one positive divisor other than 1 and itself (more than two positive divisors).
Remember
n is composite ↔ n > 1 and n has a divisor d with 1 < d < n
Buckets for positive integers:
n = 1 → neither prime nor composite
prime → exactly two divisors (1 and n)
composite → more than two divisors
Smallest composite: 4 (= 2 × 2)
n
Divisors
Class
1
1
Neither
2
1, 2
Prime
4
1, 2, 4
Composite
12
1, 2, 3, 4, 6, 12
Composite
Approach
How to Check a Composite Number in C++
Reject n ≤ 1, then look for any divisor from 2 through √n.
If n <= 1, return false (not composite).
Try every i from 2 while i * i <= n.
If any n % i == 0, return true.
Otherwise return false (prime, for n > 1).
Method
Idea
Time
Best for
√n trial division
Find any factor ≤ √n
O(√n)
Interviews, default
Range scan
Reuse the helper
O(N√N)
Listing composites
Witness factor
Return the first divisor
O(√n)
Explain why
Pseudocode
Pseudocode
function IsComposite(n):
if n <= 1:
return false
for i from 2 to floor(sqrt(n)):
if n mod i == 0:
return true
return false
Reference
Cheat Sheet
Keep these facts handy while writing the program.
Topic
Detail
Test
n > 1 and has a factor in 2..√n
1
Neither prime nor composite
Smallest
4
1..10
4, 6, 8, 9, 10
Loop bound
i * i <= n (integer-safe)
Try it
Live Preview
Enter a positive integer to see whether it is composite, prime, or neither.
Positive whole numbers. Tap a chip or type a value.
Result
n = 12
Divisible by 2
Verdict: COMPOSITE
Trace
Worked Walkthrough — n = 12
Look for any factor from 2 through √12 ≈ 3.46.
Calculation
n = 12 (n > 1 ✓)
Try i = 2 .. floor(√12) = 3
i = 2: 12 % 2 == 0 ✓
Found a factor → composite
(12 = 2 × 6)
Code
C++ Programs
Start with a boolean √n check. Then list a range, and finish by returning a witness factor.
Example 1 — Check One Number
Short function, fast early return, and integer-safe loop bound.
C++
#include <iostream>
bool isComposite(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return true;
}
}
return false;
}
int main() {
int n = 12;
if (isComposite(n)) {
std::cout << n << " is a composite number.\n";
} else {
std::cout << n << " is not a composite number.\n";
}
return 0;
}
Output
12 is a composite number.
How It Works
Return false immediately when n <= 1.
Loop while i * i <= n (avoids floating sqrt).
Any divisor found means composite — return true.
If the loop finishes, n has no nontrivial factor ≤ √n.
For 12, i = 2 divides immediately.
Example 2 — Composite Numbers from 1 to 10
Print only values that satisfy the composite test.
C++
#include <iostream>
bool isComposite(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return true;
}
}
return false;
}
int main() {
std::cout << "Composite numbers in the range 1 to 10 are:\n";
for (int num = 1; num <= 10; num++) {
if (isComposite(num)) {
std::cout << num << " ";
}
}
std::cout << "\n";
return 0;
}
Output
Composite numbers in the range 1 to 10 are:
4 6 8 9 10
How It Works
Reuse the same √n helper for every value.
Loop from 1 to 10 and print matches.
1 is skipped (neither); 2, 3, 5, 7 are prime.
Composites printed: 4, 6, 8, 9, 10.
Useful self-check when rewriting the function.
Example 3 — Find a Witness Factor
If composite, report one divisor that proves it.
C++
#include <iostream>
/** Return a nontrivial divisor, or -1 if not composite. */
int firstFactor(int n) {
if (n <= 1) {
return -1;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return i;
}
}
return -1;
}
int main() {
int samples[] = { 12, 7, 1, 9 };
int count = sizeof(samples) / sizeof(samples[0]);
for (int i = 0; i < count; i++) {
int n = samples[i];
int f = firstFactor(n);
if (f == -1) {
const char* label = n <= 1 ? "neither" : "prime";
std::cout << n << ": not composite (" << label << ")\n";
} else {
std::cout << n << ": composite (divisible by " << f << ")\n";
}
}
return 0;
}
Output
12: composite (divisible by 2)
7: not composite (prime)
1: not composite (neither)
9: composite (divisible by 3)
How It Works
Same loop as isComposite, but return the divisor.
Return -1 when no nontrivial factor exists.
Label n <= 1 as neither; otherwise as prime.
12 yields factor 2; 9 yields factor 3.
Handy when the follow-up is “show me a factor.”
Edge Cases & Pitfalls
Check these before calling the solution done.
n = 1
Neither prime nor composite
Always return false for composite. Do not call 1 prime either.
2, 3
Small primes
The √n loop never runs (or finds no factor). Correctly not composite.
Bound
Use i * i <= n
Safer than casting sqrt to int. Avoids floating-point off-by-ones.
Negatives
Usually not classified
Composite/prime definitions apply to integers greater than 1.
Analysis
Time and Space Complexity
Program
Time
Extra space
Single check / witness
O(√n)
O(1)
Range 1..N
O(N√N)
O(1)
Worst case is a prime (or 1): the loop runs through all candidates up to √n.
Remember
Key Takeaways
Definition: n > 1 with a factor other than 1 and n.
Smallest: 4.
Check: trial division with i * i <= n.
1: neither prime nor composite.
One line: if n > 1 and any factor ≤ √n exists, it is composite.
Frequently Asked Questions
An integer greater than 1 that has at least one positive divisor other than 1 and itself. The smallest composite number is 4.
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.
If n has a factor larger than √n, it also has a paired factor smaller than √n.
The optimized check is O(√n) time and O(1) extra space.
