Optimizing Prime Checks with Go (Golang)

The efficiency of the prime-checking algorithm can be improved by only checking for divisibility up to the square root of the number, as any factor larger than that would necessarily pair with a factor smaller than the square root. Here's a more efficient version of the isPrime function:

package main

import (
    "fmt"
    "math"
)

func isPrime(n int) (bool, string) {
    // 0 and 1 are not prime
    if n == 0 || n == 1 {
        return false, fmt.Sprintf("%d is not prime, by definition!", n)
    }

    // negative numbers are not prime
    if n < 0 {
        return false, "Negative numbers are not prime, by definition!"
    }

    // Special case: 2 is prime
    if n == 2 {
        return true, fmt.Sprintf("%d is a prime number!", n)
    }

    // Any even number other than 2 is not prime
    if n%2 == 0 {
        return false, fmt.Sprintf("%d is not a prime number because it is divisible by 2", n)
    }

    // Check only up to the square root of n and only check odd divisors
    sqrtN := int(math.Sqrt(float64(n)))
    for i := 3; i <= sqrtN; i += 2 {
        if n%i == 0 {
            return false, fmt.Sprintf("%d is not a prime number because it is divisible by %d", n, i)
        }
    }

    return true, fmt.Sprintf("%d is a prime number!", n)
}

func main() {
    // Example usage
    num := 29
    isPrimeNum, msg := isPrime(num)
    fmt.Println(msg)
}

Key Points:

• Checking only up to square root of n: After considering the special cases, the loop only checks divisibility for numbers up to sqrt(n).

• Skipping even numbers: Since we've already checked for n = 2 as a special case, and any other even number will be divisible by 2 and hence not prime, we can safely start the loop at 3 and increment by 2. This way, we only check odd numbers as potential divisors.

FAQ: Why Checking only up to square root of n?

The reasoning for checking only up to the square root of n when determining if n is prime is based on the properties of factors.

Imagine if n is divisible by a number x which is greater than the square root of n. Then, there must also be another number y such that: X x Y = n

Now, since x is greater than the square root of n, y must be smaller than the square root of n for their product to be n. Think of it this way: if both x and y were greater than the square root of n, their product would exceed n. Similarly, if both were less than the square root of
n, their product would be less than n.

So, if n has a factor greater than its square root, it will also have a factor smaller than its square root. This is why, to determine if n is prime, we only need to check for factors up to and including its square root. If we haven't found any factors in that range, then n doesn't have any factors and is therefore prime.

To illustrate, let's use a number, say n=100. The square root of 100 is 10. If n has a factor greater than 10 (like 20), it will necessarily have a corresponding factor smaller than 10 (like 5, since 20 x 5 = 100). By checking up to 10, we'll catch the factor of 5, so we don't need to check factors greater than 10.