12Composite
Check Composite Number in PHP
What you’ll learn
- Composite vs prime definition.
- n/2 and sqrt(n) trial-division checks.
- Range scan and edge cases.
Overview
A number n>1 is composite if it has a factor between 1 and n.
Prerequisites
Loops and modulo checks.
for,if,%.- Basic integer comparisons.
What is a composite number?
Composite means n > 1 and n has more than two positive divisors.
Trial division bound
If n is composite, at least one factor is <= sqrt(n).
Intuition
7Prime
Live preview
Algorithm
Goal: decide if n is composite.
1
If n <= 1 return false.
2
Try divisors from 2 to sqrt(n).
3
If any divides n, return true; else false.
📜 Pseudocode
Pseudocode
if n <= 1: not composite
for i from 2 while i*i <= n:
if n % i == 0: composite
not composite1
Classic check up to n/2
php
<?php
function isCompositeHalf(int $n): bool
{
if ($n <= 1) return false;
for ($i = 2; $i <= intdiv($n, 2); $i++) {
if ($n % $i === 0) return true;
}
return false;
}
$num = 12;
echo isCompositeHalf($num) ? "$num is a composite number." : "$num is not a composite number.";
?>2
sqrt test and range scan
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 . " ";
}
?>Optimization
Use sqrt bound for faster checks.
Stop early as soon as one factor is found.
❓ FAQ
An integer n > 1 that has a divisor other than 1 and itself.
No. 1 is neither prime nor composite.
No, 2 is prime.
If n has a factor, at least one factor is <= sqrt(n), so checking further is unnecessary.
Single check with sqrt bound is O(sqrt(n)) time and O(1) space.
🔄 Input / output examples
| n | Composite? |
|---|---|
12 | Yes |
7 | No |
1 | No (neither) |
Edge cases and pitfalls
1
Neither prime nor composite
Don’t mark 1 as composite.
2
Prime
Smallest prime; not composite.
⏱️ Time and space complexity
| Method | Time | Extra space |
|---|---|---|
| up to n/2 | O(n) | O(1) |
| up to sqrt(n) | O(√n) | O(1) |
Summary
- Composite means n > 1 and not prime.
- Trial division is standard method.
- sqrt-bound version is faster.
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