素数伴侣

package main

import (
	"bufio"
	"fmt"
	"os"
    "sort"
)

const MAX = 60000 + 1 // a+b 最大 60000

var isPrime [MAX]bool

// 线性筛法预处理素数
func sieve() {
    // 从2开始，先初始化为都是素数
    for i:=2;i<MAX;i++{
        isPrime[i] = true
    }
	for i:=2;i<MAX;i++{
        if isPrime[i] {
            for j:= i*i;j<MAX;j+=i{ // 素数的倍数不是素数
                isPrime[j] = false
            }
        }
    }
}

/* 
    素数是奇数+偶数
    二分图配对问题
    以个数少的一方为配对基准（左图left）
    优先对left中可匹配right图数较少的元素进行配对

    步骤：
    1）素数集求解
    2）读取数据
    3）奇偶分离（二分）
    4）可配对情况 邻接表adj
    5）尝试配对 函数dfs —— 匈牙利算法
    6）开始配对，并输出结果
 */

func main() {
    /* 1）素数集求解 */
	sieve()

    /* 2）读取数据 */
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	// 读 n
	scanner.Scan()
	var n int
	fmt.Sscan(scanner.Text(), &n)

	// 读 n 个数
	nums := make([]int, n)
	for i := 0; i < n; i++ {
		scanner.Scan()
		fmt.Sscan(scanner.Text(), &nums[i])
	}

    /* 3）奇偶分离（二分） */
	// 分离奇偶
    var odds, evens []int
    for i:=0;i<n;i++{
        if nums[i]%2 ==0{
            evens =append(evens, nums[i])
        }else{
            odds = append(odds, nums[i])
        }
    }

    // 决定哪边做左部（如果个数相差较大）：选个数少的
    evensLessOdd :=  float64((len(odds) - len(evens)))/float64(len(evens)) > 0.2

    var left, right []int
    var adj [][]int

    if evensLessOdd {
        left, right = evens, odds
    } else {
        left, right = odds, evens
    }

    /* 4）可配对情况 邻接表adj */
    // 构建邻接表：left[i] 能和哪些 right[j] 配对
    adj = make([][]int, len(left)) // 记录left和right中元素的索引，而非数值
    var t int
    for i:= 0;i<len(left);i++{
        for j:=0;j<len(right);j++{
            t = left[i]+right[j]
            if t < MAX && isPrime[t] {
                adj[i] = append(adj[i], j)
            }
        }
    }

    // （可选，由于一般相差不大，排序未必更高效）在构建 adj 后，按可匹配数升序排序 left
    indices := make([]int, len(left))
    for i := range indices {
        indices[i] = i
    }
    sort.Slice(indices, func(i, j int) bool {
        return len(adj[indices[i]]) < len(adj[indices[j]])
    })

    // 重新排序 adj（和 left，如果需要）
    newAdj := make([][]int, len(left))
    for i, idx := range indices {
        newAdj[i] = adj[idx]
    }
    adj = newAdj

    /* 5）尝试配对 函数dfs */
	// 匈牙利算法求最大匹配
	matchRight := make([]int, len(right)) // matchRight[j] = 哪个 left 的索引匹配了 right[j]
	for i:=0;i<len(matchRight);i++{
        matchRight[i] = -1 // -1 表示未匹配
    }
    var dfs func(u int, visited []bool) bool 
    dfs = func(u int, visited []bool) bool {
        for _, i := range adj[u] {
            if visited[i]{
                continue
            }
            visited[i] = true
            if matchRight[i] == -1 || dfs(matchRight[i], visited) {
                matchRight[i] = u
                return true
            }
        }
        return false
    }

    /* 6）开始配对，并输出结果 */
    var matching int =0
    for i:=0;i<len(left);i++ {
        visited := make([]bool, len(right))
        if dfs(i, visited){
            matching++
        }
    }

	fmt.Println(matching)
}

package main

import (
	"fmt"
)

func isPrime(n int) bool {
	if n < 2 {
		return false
	}

	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

func getMax(nums []int) int {
	res := 0

	// 按奇偶划分
	odds := []int{}
	evens := []int{}
	for i := 0; i < len(nums); i++ {
		if nums[i]&1 == 1 {
			odds = append(odds, nums[i])
		} else {
			evens = append(evens, nums[i])
		}
	}

	n := len(evens)

	// 为每个奇数寻找匹配的偶数
	// 采用的策略：先到先得, 能让则让
	// 先到先得：如果该偶数的匹配为0，就直接与之匹配
	// 能让则让：如果该偶数已经匹配(匹配不为零)，那么为与之匹配的奇数重新寻找匹配，如果能找到新的匹配，那么就把该偶数让给当前奇数
	// 否则该奇数不能找到匹配
	visited := make([]bool, n) //记录第i个偶数在本轮匹配中是否被访问过
	matched := make([]int, n)  //记录与第i个偶数匹配的奇数
	var match func(int) bool   //检查该奇数是否能找到合适的匹配, 注意：这是一个闭包函数
	match = func(odd int) bool {
		for i := 0; i < n; i++ {
			if isPrime(odd+evens[i]) && !visited[i] {
				visited[i] = true
				if matched[i] == 0 || match(matched[i]) {
					matched[i] = odd
					return true
				}
			}
		}
		return false
	}

	// 为每个奇数寻找匹配
	// 每轮的 visited 要清空
	for _, odd := range odds {
		visited = make([]bool, n)
		if match(odd) {
			res++
		}
	}

	return res
}

func main() {
	var n int
	fmt.Scanf("%d", &n)

	nums := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &nums[i])
	}
	fmt.Println(getMax(nums))
}

GO语言实现 匈牙利算法

package main
import "fmt"
import "io"
import "math"

func main(){
    for {
        var n int
        var num int
        var odds []int
        var evens []int
        c, err := fmt.Scanf("%d\n", &n)
        if c==0 || err==io.EOF{
            break
        }
        for i:=0; i<n; i++{
            fmt.Scanf("%d", &num)
            if num % 2 == 0{
                evens = append(evens, num)
            }else{
                odds = append(odds, num)
            }
        }
        var suited map[int]int = make(map[int]int)
        var K int
        for i:=0; i<len(odds); i++{
            var visited map[int]int = make(map[int]int)
            ok := match(odds[i], evens, visited, suited)
            if ok {
                K++
            }
        }
        fmt.Println(K)
    }
}
func match(odd int, evens []int, visited map[int]int, suited map[int]int) bool {
    for _, even := range evens{
        if isPrime(odd + even) && visited[even] == 0 {
            visited[even] = 1
            if suited[even] == 0 || match(suited[even], evens, visited, suited) {
                suited[even] = odd
                return true
            }
        }
    }
    return false
}
func isPrime(num int) bool {
    n := math.Sqrt(float64(num))
    n2 := int(n + 0.5)
    for i := 2; i <= n2; i++{
        if num%i == 0{
            return false
        }
    }
    return true
}

package main

import (
    "bufio"
    "fmt"
    "math/big"
    "os"
    "strconv"
    "strings"
)

func main() {


    scan := bufio.NewScanner(os.Stdin)
    for {
        scan.Scan()
        nums := scan.Text()
        if nums == "" {
            break
        }
        numsList := strings.Split(nums, " ")
        if len(numsList) == 1 {
            continue
        }
        numList := make([]int, 0, len(numsList))
        for _, v := range numsList {
            num, _ := strconv.Atoi(v)
            numList = append(numList, num)
        }
        ji, ou := GroupList(numList)
        result := 0
        match := make([]int, len(ou))
        for i:= 0; i < len(ji); i ++ {
            used := make([]int, len(ou))
            if find(ji[i], used, match, ou) {
                result ++
            }
        }
        fmt.Println(result)
    }

}

// 分奇偶
func GroupList(n []int) ([]int, []int) {
    odd := make([]int, 0, len(n))
    even := make([]int, 0, len(n))
    for _, v := range n {
        if v %2 ==  1 {
            odd = append(odd, v)
            continue
        }
        even = append(even, v)
    }
    return odd, even
}

func find(x int, l1, l2, l3 []int) bool {
    for i := 0; i < len(l3); i ++ {
        if big.NewInt(int64(l3[i] + x)).ProbablyPrime(0) && l1[i] == 0 {
            l1[i] = 1
            if l2[i] == 0 || find(l2[i], l1, l2, l3) {
                l2[i] = x
                return true
            }
        }
    }
    return false
}