题目描述 在一个古老的村庄中，有一种神秘的涂色仪式。这个村庄有一个复杂的树状结构，每个节点都有一个特定的权值。在仪式开始时，所有的节点都是黑色的。 但是，村民们发现了一些奇特的规则，只要相邻的两个结点满足以下两个条件： 颜色都是黑色 权值之和是质数 村民们就可以选择其中一个节点变成白色。你的任务是确定在这些条件下，最多可以有多少节点变成白色。

分析: 想象成一棵树,把相邻两个节点的权值相加,再判断它是不是质数,不是就cnt++(cnt统计有多少个节点没有涂色,每有一对权值之和不是质数,就有一个点不会涂色)。 最后输出总结点数-1-cnt就可以了。 在这之前要先找出质数有哪些,用循环容易超时,建议使用埃氏筛或线性筛(欧拉筛)。

错因:最开始的代码循环太多了,而且找质数也没用埃氏筛,导致超时。

代码:

/*  
思路很简单 
把它想象成一棵树,将两条相邻的边上的权值相加,看是不是质数,不是就cnt++(cnt是统计不会染色节点个数)
最后输出n-1-cnt(其中n是总节点数,-1是因为最多只会有n-1个点染成白色)

数据范围
n最大是3*10^5,每个点的权值最大是10^6,开int可能会超,建议开long long 
*/
#include<bits/stdc++.h>
using namespace std;
int a[1000010];
bool b[2000010];
long long n,cnt;
void f(){
	for(int i=2;i<=2000000;i++){
		if(b[i]) continue;
		for(int j=2*i;j<=2000000;j+=i){
			b[j]=1;
		}
	}
	return ;
}
int main(){
 	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout); 
	cin>>n;
	f();
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	long long u,v;
	for(int i=1;i<n;i++){
		cin>>u>>v;
		if(b[a[u]+a[v]]){
			cnt++;
		}
	}
	cout<<n-1-cnt;
	return 0;
}