Prime Number Program in Golang

In this blog post, we'll explore the concept of prime numbers and demonstrate how to check if a number is prime using the Go (Golang) programming language. 

Prime numbers play a crucial role in various mathematical and computer science applications. We'll discuss two different approaches to determine if a given number is a prime number.

An approach using Trial Division

The most straightforward method to check if a number is prime is through trial division. In this approach, we divide the number by all integers from 2 to the square root of the number. If any of these divisions result in a remainder of zero, then the number is not prime. Otherwise, it is prime.

package main

import (
	"fmt"
	"math"
)

func isPrime(number int) bool {
	if number <= 1 {
		return false
	}

	// Loop to check divisibility
	for i := 2; i <= int(math.Sqrt(float64(number))); i++ {
		if number%i == 0 {
			return false
		}
	}
	return true
}

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

Output:

17 is a prime number.

An approach using the Sieve of Eratosthenes

The Sieve of Eratosthenes is an optimized algorithm to find all prime numbers up to a given limit. Although this method is not suitable for checking primality for a single number, it provides an efficient way to generate prime numbers and can be used to precompute prime numbers within a certain range.

package main

import "fmt"

func sieveOfEratosthenes(limit int) []bool {
	sieve := make([]bool, limit+1)

	// Initialize all elements as true
	for i := 2; i <= limit; i++ {
		sieve[i] = true
	}

	// Apply the sieve algorithm
	for p := 2; p*p <= limit; p++ {
		if sieve[p] == true {
			for i := p * p; i <= limit; i += p {
				sieve[i] = false
			}
		}
	}

	return sieve
}

func isPrimeUsingSieve(number int) bool {
	if number <= 1 {
		return false
	}
	sieve := sieveOfEratosthenes(number)
	return sieve[number]
}

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

Output:

17 is a prime number.

Conclusion

In this blog post, we explored two different methods to check if a number is prime using the Go programming language. The trial division method provides a straightforward approach for checking primality, while the Sieve of Eratosthenes offers an efficient way to generate prime numbers within a given range. 

Depending on your specific use case, you can choose the appropriate method. Understanding prime numbers and their properties can be beneficial in various mathematical and algorithmic applications. Happy coding in Golang!