I recently created a program which will tell you if a number is prime or not. It gets all answers right but the prime number of 9.
package main
import "fmt"
func isPrime(num int) bool {
for x := 2; x > 1; x++ {
if num%2 == 0 {
return false
} else {
return true
}
}
return true
}
func main() {
fmt.Printf("is it a prime number: %v
", isPrime(9))
}
What is the problem?
Thanks in advance!
1- Here is the working version of your code: try it on The Go Playground.
package main
import "fmt"
func isPrime(num int) bool {
if num < 2 {
return false
}
for x := 2; x < num; x++ {
if num%x == 0 {
return false
}
}
return true
}
func main() {
fmt.Printf("is it a prime number: %v
", isPrime(9))
}
2- The only even prime is 2, so it is better to check it first:
if n == 2 {
return true
}
Then there is no other even prime number: remove them all, and there is no prime number less than 2:
if n < 2 || n&1 == 0 {
return false
}
and you don't need to check more than square root of n
:
sqrt := int(math.Sqrt(float64(n)))
And now you may start from 3, with just odd numbers (i += 2
):
for i := 3; i <= sqrt; i += 2 {
if n%i == 0 {
return false
}
}
Try it on The Go Playground:
package main
import (
"fmt"
"math"
)
func isPrime(n int) bool {
if n == 2 {
return true
}
if n < 2 || n&1 == 0 {
return false
}
sqrt := int(math.Sqrt(float64(n)))
for i := 3; i <= sqrt; i += 2 {
if n%i == 0 {
return false
}
}
return true
}
func main() {
fmt.Printf("is it a prime number: %v
", isPrime(9))
for i := 0; i < 120; i++ {
if isPrime(i) {
fmt.Print(i, " ")
}
}
fmt.Println()
}
output:
is it a prime number: false
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113
As it is, your code is only checking if a number's parity and returning false if it is even. I don't actually know Go, but I did manage to work out this problem for you using the following code:
func isPrime(num int) bool {
for x := 2; x < num; x++{
if num%x == 0 && num!=2{
return false
}
}return true;
}
According to prime number definition A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself, in your code you're only checking if it's odd or not.
I left you a fast solution in Go https://play.golang.org/p/2XXTUFbjhy It does only go until the square root of the number.
func isPrime(n int) bool {
if n <= 1 {
return false
}
for ix, sqn := 2, int(math.Sqrt(float64(n))); ix <= sqn; ix++ {
if n%ix == 0 {
return false
}
}
return true
}
Also if you're interested in a faster way to know if a number is primer or not I recommend you read about the Sieve of Eratosthenes