1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| func countPaths(n int, edges [][]int) int64 {
primes := prime(n)
grip := [][]int{}
for i := 0; i <= n; i++ {
grip = append(grip, []int{})
}
for _, edge := range edges {
grip[edge[0]] = append(grip[edge[0]], edge[1])
grip[edge[1]] = append(grip[edge[1]], edge[0])
}
var dfs func(cur, parent int, nodes *[]int)
dfs = func(cur, parent int, nodes *[]int) {
*nodes = append(*nodes, cur)
for _, edge := range grip[cur] {
if primes[edge] && edge != parent {
dfs(edge, cur, nodes)
}
}
}
sumArr := make([]int, n+1)
ans := int64(0)
for i := 2; i <= n; i++ {
if primes[i] {
continue
}
sum := 0
for _, edge := range grip[i] {
if !primes[edge] {
continue
} else if sumArr[edge] == 0 {
nodes := []int{}
dfs(edge, -1, &nodes)
for _, node := range nodes {
sumArr[node] = len(nodes)
}
}
ans += int64(sum * sumArr[edge])
sum += sumArr[edge]
}
ans += int64(sum)
}
return ans
}
func prime(n int) []bool {
primes := make([]bool, n+1)
primes[1] = true
for i := 2; i <= n; i++ {
if !primes[i] {
for j := i * i; j <= n; j += i {
primes[j] = true
}
}
}
return primes
}
|
