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.
Top comments (0)