Skip to content

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, 511 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 := 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 }
Code language: Go (go)

Option 2:

package solution func Solve(a, b int) (sum int) { primes := make([]int, , 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 := ; primes[i]*primes[i] <= next; i++ { if next%primes[i] == { 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 }
Code language: Go (go)

Option 3:

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

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(,10, 8) dotest(2,200, 1080) dotest(1000,100000,52114889) dotest(4000,500000,972664400) }) })
Code language: Go (go)

See also  Sort Lexicographical Order of Substrings in Java
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x