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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
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)
})
})
|
