Go Program to Check Prime Number with Example

In Go, you can check if a number is prime by writing a function that tests divisibility from 2 up to the square root of the number using a loop and the % operator; for example, func isPrime(n int) bool { if n <= 1 { return false } for i := 2; i*i <= n; i++ { if n % i == 0 { return false } } return true }.

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. Start checking from 2 up to the square root of the number because if a larger factor exists, a smaller one must also exist. If you find any number that divides it evenly, the number is not prime; otherwise, it is prime.

Algorithm

1

Get the input number.

2

If the number is less than or equal to 1, return false (not prime).

3

Loop from 2 to the square root of the number.

4

For each number in the loop, check if it divides the input number evenly.

5

If any number divides evenly, return false (not prime).

6

If no divisors found, return true (prime).

Code

go

package main

import (
	"fmt"
	"math"
)

func isPrime(n int) bool {
	if n <= 1 {
		return false
	}
	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

func main() {
	n := 17
	if isPrime(n) {
		fmt.Printf("%d is a prime number\n", n)
	} else {
		fmt.Printf("%d is not a prime number\n", n)
	}
}

Output

17 is a prime number

Dry Run

Let's trace the number 17 through the code to see how it checks for primality.

1

Check if number is <= 1

17 is greater than 1, so continue.

2

Calculate square root limit

Square root of 17 is approximately 4.12, so loop from 2 to 4.

3

Loop and check divisibility

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

4

No divisors found

Return true, 17 is prime.

i	n % i	Divides evenly?
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 or equal to 1 are not prime by definition, so we return false immediately.

Step 2: Check divisors up to square root

We only check divisors up to the square root because any factor larger than that would have a matching smaller factor already checked.

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

go

package main

import "fmt"

func isPrime(n int) bool {
	if n <= 1 {
		return false
	}
	for i := 2; i < n; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

func main() {
	fmt.Println(isPrime(17))
}

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

Use a sieve algorithm (Sieve of Eratosthenes)

go

package main

import "fmt"

func sieve(n int) []bool {
	prime := make([]bool, n+1)
	for i := 2; i <= n; i++ {
		prime[i] = true
	}
	for p := 2; p*p <= n; p++ {
		if prime[p] {
			for i := p * p; i <= n; i += p {
				prime[i] = false
			}
		}
	}
	return prime
}

func main() {
	primes := sieve(20)
	for i := 2; i <= 20; i++ {
		if primes[i] {
			fmt.Printf("%d is prime\n", i)
		}
	}
}

This method finds all primes up to n efficiently but is more complex and uses more memory.

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

Time Complexity

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

Space Complexity

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

Which Approach is Fastest?

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

Approach	Time	Space	Best For
Check up to √n	O(√n)	O(1)	Single number primality check
Check up to n-1	O(n)	O(1)	Simple but slower primality check
Sieve of Eratosthenes	O(n log log n)	O(n)	Finding all primes up to n