leetcode-go/oj/tencent-2017-autumn/prime-pair.go

package main

import (
	"fmt"
	"math"
)

func main() {
	var n int
	fmt.Scan(&n)
	sieve := make([]bool, n+1)
	prime := make([]int, 0)
	sqrt := int(math.Sqrt(float64(n)))
	for i := 2; i <= sqrt; i++ {
		if sieve[i] {
			continue
		}
		for j := 2 * i; j <= n; j += i {
			sieve[j] = true
		}
	}
	for i := 2; i <= n; i++ {
		if !sieve[i] {
			prime = append(prime, i)
		}
	}
	cnt := 0
	m := make(map[int]bool)
	for _, p := range prime {
		if m[n-p] || 2*p == n {
			cnt++
		}
		m[p] = true
	}
	fmt.Println(cnt)
}