Software Engineering

# How to Calculate Dominant Primes in Golang

## The challenge#

The prime number sequence starts with: `2,3,5,7,11,13,17,19...`. Notice that `2` is in position `one`.

`3` occupies position `two`, which is a prime-numbered position. Similarly, `5``11` and `17` also occupy prime-numbered positions. We shall call primes such as `3,5,11,17` dominant primes because they occupy prime-numbered positions in the prime number sequence. Let’s call this `listA`.

As you can see from listA, for the prime range `range(0,10)`, there are `only two` dominant primes (`3` and `5`) and the sum of these primes is: `3 + 5 = 8`.

Similarly, as shown in listA, in the `range (6,20)`, the dominant primes in this range are `11` and `17`, with a sum of `28`.

Given a `range (a,b)`, what is the sum of dominant primes within that range? Note that `a <= range <= b` and `b` will not exceed `500000`.

## The solution in Golang#

Option 1:

``````package solution
func Solve(a, b int) int {
sum := 0
sv := make([]bool, b+1)
pos := 1
if a <= 3 && b >= 3 {
sum += 3
}
for i := 3; i <= b; i += 2 {
if sv[i] == false {
pos++
if i >= a && pos%2 == 1 && sv[pos] == false {
sum += i
}
for j := i + i; j <= b; j += i {
sv[j] = true
}
}
}
return sum
}
``````

Option 2:

``````package solution
func Solve(a, b int) (sum int) {
primes := make([]int, 0, 5000)
primes = append(primes, 2, 3, 5, 7)
prime := func(n int) int {
for n > len(primes) {
next := primes[len(primes) - 1] + 1
for i := 0; primes[i]*primes[i] <= next; i++ {
if next%primes[i] == 0 { next += 1 ; i = -1 }
}
primes = append(primes, next)
}
return primes[n-1]
}
for i := 1 ;; i++ {
dominantPrime := prime(prime(i))
if dominantPrime > b { break }
if dominantPrime < a { continue }
sum += dominantPrime
}
return
}
``````

Option 3:

``````package solution
func isPrime(n int) bool {
for i := 2; i*i < n+i; i++ {
if n%i == 0 {
return false
}
}
return n > 1
}
func Solve(a, b int) int {
c, pos := 0, 0
for i := 0; i <= b; i++ {
if isPrime(i) {
pos++
if i >= a && isPrime(pos) {
c += i
}
}
}
return c
}
``````

## Test cases to validate our solution#

``````package solution_test
import (
. "github.com/onsi/ginkgo"
. "github.com/onsi/gomega"
)
func dotest(s, g, exp int) {
var ans = Solve(s,g)
Expect(ans).To(Equal(exp))
}
var _ = Describe("Example tests", func() {
It("It should work for basic tests", func() {
dotest(0,10, 8)
dotest(2,200, 1080)
dotest(1000,100000,52114889)
dotest(4000,500000,972664400)
})
})
``````