Challenge 22 - Largest Pandigital Prime
Problem Attribution - This challenge was inspired by Problem 41 on Project Euler
👋 Welcome Gophers! In this challenge, you are tasked with implementing the LargestPandigitalPrime function which will return the largest possible pandigital prime number.
Pandigital Primes
An n-digit number is pandigital if it makes use of all the digits 1 to n exactly ones.
pandigital := LargestPandigitalPrime() // returns largest pandigital prime
View Solution
package main
import (
"fmt"
"math"
"strconv"
)
func notPrime(n int) bool {
if n&2 == 2 {
return false
}
if (n-1)%6 == 0 {
return false
}
if (n+1)%6 == 0 {
return false
}
return true
}
func isPrime(n int) bool {
if notPrime(n) {
return false
}
max := int(math.Ceil(math.Sqrt(float64(n))))
for i := int(3); i < max; i += 2 {
if n%i == 0 {
return false
}
}
return true
}
func atoi(s string) int {
n, _ := strconv.Atoi(s)
return n
}
func permute(s string) []string {
if len(s) == 1 {
return []string{s}
}
perms := []string{}
head := string(s[0])
tail := s[1:]
for _, perm := range permute(tail) {
for i := 0; i < len(s); i++ {
newperm := perm[:i] + head + perm[i:]
perms = append(perms, newperm)
}
}
return perms
}
func LargestPandigitalPrime() int {
max := 0
digits := "7654321"
for i := 0; i < len(digits); i++ {
for _, perm := range permute(digits[i:]) {
i := atoi(perm)
if isPrime(i) {
if i > max {
max = i
}
}
}
if max > 0 {
break
}
}
return max
}
func main() {
fmt.Println("Pandigital Primes")
pandigitalPrime := LargestPandigitalPrime()
fmt.Println(pandigitalPrime)
}
Further Reading:
If you enjoyed this challenge, you may also like some of the other challenges on the site!