PHP Program to Check Prime Number with Output

Use a PHP program that checks if a number is less than 2, then loops from 2 to the square root of the number using for and checks divisibility with % operator to determine if it's prime.

Examples

Input2

Output2 is a prime number.

Input15

Output15 is not a prime number.

Input17

Output17 is a prime number.

How to Think About It

To check if a number is prime, first exclude numbers less than 2 because primes start from 2. Then, test if the number can be divided evenly by any number from 2 up to its square root. If it can, it's not prime; otherwise, it is.

Algorithm

1

Get the input number.

2

If the number is less than 2, return not prime.

3

Loop from 2 to the square root of the number.

4

If the number is divisible by any number in the loop, return not prime.

5

If no divisors found, return prime.

Code

php

<?php
function isPrime(int $num): bool {
    if ($num < 2) {
        return false;
    }
    $limit = (int) sqrt($num);
    for ($i = 2; $i <= $limit; $i++) {
        if ($num % $i === 0) {
            return false;
        }
    }
    return true;
}

$number = 17;
if (isPrime($number)) {
    echo "$number is a prime number.";
} else {
    echo "$number is not a prime number.";
}

Output

17 is a prime number.

Dry Run

Let's trace the number 17 through the code to check if it is prime.

1

Check if number is less than 2

17 is not less than 2, so continue.

2

Calculate square root limit

Square root of 17 is about 4.12, so limit is 4.

3

Loop from 2 to 4 and check divisibility

Check 17 % 2, 17 % 3, 17 % 4; none are zero.

4

No divisors found

Return true, 17 is prime.

i	num % i	Divisible?
2	17 % 2 = 1	No
3	17 % 3 = 2	No
4	17 % 4 = 1	No

Why This Works

Step 1: Exclude numbers less than 2

Numbers less than 2 are not prime by definition, so we return false immediately.

Step 2: Check divisors up to square root

If a number has a divisor larger than its square root, it must also have a smaller one, so checking up to the square root is enough.

Step 3: Return result based on divisibility

If any divisor divides the number evenly, it is not prime; otherwise, it is prime.

Alternative Approaches

Check divisibility up to n-1

php

<?php
function isPrime(int $num): bool {
    if ($num < 2) {
        return false;
    }
    for ($i = 2; $i < $num; $i++) {
        if ($num % $i === 0) {
            return false;
        }
    }
    return true;
}

$number = 17;
if (isPrime($number)) {
    echo "$number is a prime number.";
} else {
    echo "$number is not a prime number.";
}

This method is simpler but slower because it checks all numbers up to n-1 instead of just up to the square root.

Use a sieve algorithm (Sieve of Eratosthenes)

php

<?php
function sievePrime(int $num): bool {
    if ($num < 2) return false;
    $sieve = array_fill(0, $num + 1, true);
    $sieve[0] = $sieve[1] = false;
    for ($i = 2; $i * $i <= $num; $i++) {
        if ($sieve[$i]) {
            for ($j = $i * $i; $j <= $num; $j += $i) {
                $sieve[$j] = false;
            }
        }
    }
    return $sieve[$num];
}

$number = 17;
if (sievePrime($number)) {
    echo "$number is a prime number.";
} else {
    echo "$number is not a prime number.";
}

This method is efficient for checking many primes at once but more complex and uses more memory.

Complexity: O(√n) time, O(1) space

Time Complexity

The loop runs up to the square root of the number, so time grows roughly with √n.

Space Complexity

Only a few variables are used, so space is constant O(1).

Which Approach is Fastest?

Checking divisibility up to the square root is faster than checking up to n-1. The sieve is faster for many numbers but uses more memory.

Approach	Time	Space	Best For
Check up to √n	O(√n)	O(1)	Single number, simple code
Check up to n-1	O(n)	O(1)	Simple but slow, not recommended
Sieve of Eratosthenes	O(n log log n)	O(n)	Many primes, batch processing