PowerShell Script to Check Prime Number with Output

Use a PowerShell script that checks divisibility from 2 up to the square root of the number with for ($i=2; $i -le [math]::Sqrt($num); $i++) { if ($num % $i -eq 0) { return $false } } to determine if a number is 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, think about whether it can be divided evenly by any number other than 1 and itself. You only need to test divisors up to the square root of the number because any larger factor would pair with a smaller one already checked.

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 in this range, return not prime.

5

If no divisors found, return prime.

Code

powershell

function Is-Prime($num) {
    if ($num -lt 2) { return $false }
    for ($i = 2; $i -le [math]::Sqrt($num); $i++) {
        if ($num % $i -eq 0) { return $false }
    }
    return $true
}

$num = 17
if (Is-Prime $num) {
    Write-Output "$num is a prime number."
} else {
    Write-Output "$num is not a prime number."
}

Output

17 is a prime number.

Dry Run

Let's trace the number 15 through the code to see if it is prime.

1

Check if number is less than 2

15 is not less than 2, continue.

2

Loop from 2 to sqrt(15) ≈ 3.87

Check divisibility by 2, 3.

3

Check divisibility

15 % 2 = 1 (not divisible), 15 % 3 = 0 (divisible), so return false.

i	num % i	Divisible?
2	15 % 2 = 1	No
3	15 % 3 = 0	Yes

Why This Works

Step 1: Check for numbers less than 2

Numbers less than 2 are not prime by definition, so the script returns $false immediately.

Step 2: Loop up to square root

Checking divisors only up to the square root reduces the number of checks needed, improving efficiency.

Step 3: Return result

If any divisor divides the number evenly, the function returns $false; otherwise, it returns $true indicating a prime.

Alternative Approaches

Check divisibility up to n-1

powershell

function Is-Prime($num) {
    if ($num -lt 2) { return $false }
    for ($i = 2; $i -lt $num; $i++) {
        if ($num % $i -eq 0) { return $false }
    }
    return $true
}

$num = 17
if (Is-Prime $num) {
    Write-Output "$num is a prime number."
} else {
    Write-Output "$num is not a prime number."
}

Simpler but slower because it checks all numbers up to n-1 instead of up to the square root.

Use a list of known primes for small numbers

powershell

function Is-Prime($num) {
    $primes = @(2,3,5,7,11,13,17,19,23,29)
    if ($primes -contains $num) { return $true }
    if ($num -lt 2) { return $false }
    for ($i = 2; $i -le [math]::Sqrt($num); $i++) {
        if ($num % $i -eq 0) { return $false }
    }
    return $true
}

$num = 29
if (Is-Prime $num) {
    Write-Output "$num is a prime number."
} else {
    Write-Output "$num is not a prime number."
}

Faster for small numbers by quick lookup but requires maintaining the list.

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

Time Complexity

The loop runs up to the square root of the input number, so the time complexity is O(√n). This is because any factor larger than the square root pairs with a smaller factor already checked.

Space Complexity

The script uses a fixed amount of extra memory regardless of input size, so space complexity is O(1).

Which Approach is Fastest?

Checking up to the square root is faster than checking all numbers up to n-1. Using a prime list is faster for small numbers but less flexible.

Approach	Time	Space	Best For
Check up to sqrt(n)	O(√n)	O(1)	General use, efficient
Check up to n-1	O(n)	O(1)	Simple but slow
Use prime list	O(1) for small n	O(k) for list size	Small numbers, quick lookup