2022.6.2 质数（素数）与合数
一、定义：
- 素数（p \neq 0, 1, -1）：当且仅当整数p除了平凡因数(即(1, p))外没有其他因数时，则称p为素数值（不可分解元素）。
2.合数(a\neq 0,1,-1)：a不是素数，则称a为合数。
二、性质：
1、如果a为合数，则必可以拆分为a=b*c（a>1 , a>b,c> 1）。
2、如果质数p有大于1的因数d，则p一定等于d。
3、大于1的合数a一定可以拆分为多个质数的乘积。
4、大于1的合数a必有质数p导致批 p | a（\sqrt{a}\geq p）。
5、质数有无穷多个。
6、大于4的质数都可以分解成6n\pm 1的形式。
证明：
一个数k（大于3）%6可能会有余数：0，1，2，3，4，5
余数0，2，4 则k必为偶数
余数为3 3+6n=3+3*2n=3*（2n+1），为合数
只剩余数1，5 为 6n+1 和 6n-1三、质数计数函数： {\color{Red} \pi (n)}
表示小于或等于n的素数的个数。
四、质数判定：
1、暴力枚举：
bool isPrime(int n){
if(n<2)return false;
for(int i=2;i<n;i++){
if(n%i==0)return false;
}
return true;
}时间复杂度O（n），容易超时。
当一个正整数的最小质因数为2时，则其最大因数值不会超过n的一半。
bool isPrime(int n){
if(n<2)return false;
for(int i=2;i<=n/2;i++){
if(n%i==0)return false;
}
return true;
}3、简单检测：
这样做是十分稳妥了，但不一定所有数都要判断。
很容易发现这样一个事实：如果a是n的约数，那么\sqrt{a}也是n的约数。
这一结论表明，在任意两个正整数的情况下，请考虑其中较小的那个数值。为了解决问题方便起见，请关注所有这些较小的数值是否都落在区间 [1, \sqrt{a}] 内。
由于1肯定是约数，所以不检验它。
bool isPrime(int n){
if(n<2)return false;
for(int i=2;i*i<=n;i++){
if(n%i==0)return false;
}
return true;
}五、筛数：
1、埃氏筛)
| 不是质数的数不筛 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 2 | |0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | |
| 3 | ||0 | 0 | 1 | 0 | 0 | 1 | 0 | ||
| 4 | ||||||||| | ||||||||
| 5 | ||||0 | 0 | 0 | 0 | 1 | ||||
| 6 | ||||||||| | ||||||||
| 7 | ||||||0 | 0 | 0 | ||||||
| 8 | ||||||||| | ||||||||
| 9 | ||||||||| | ||||||||
| 结果 | 质数 | 质数 | 合数 | 质数 | 合数 | 质数 | 合数 | 合数 | 合数 |
先用2去筛，即把2留下，把2的倍数剔除掉
再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；
接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；
不断重复下去…
void ass(int n){
bool vis[n+1];
int prime[n+1],len=0;
for(int i=2;i<=n;i++){
if(!vis[i]){
prime[++len]=i;
for(int j=2;i*j<=n;j++){
vis[i*j]=1;
}
}
}
}2、欧拉筛：
在埃氏筛的运算中，10被算了两次，特别浪费。
void ols(int n){
int a[n+1],b[n+1];
for(int i=2;i<=n;i++){
if(a[i]==0){
b[++k]=i;
}
for(int j=1;i*j<=n;j++){
if(i*b[j]>n)break;
a[i*b[j]]=1;
if(i%b[j]==0)break;
}
}
}六、真题演练：洛谷（P2441 角色属性树）
题目描述：
这个"绪萌同人社"组织具有一定的趣味性。从组织架构来看，则呈现出一种典型的树状结构：此类型下的领导层配置中包含一个主要负责人，在其手下配置若干副总负责人；在这一层级中，则会依次配置若干部门负责人……
每一个角色都具有独特的萌点属性，在这个属性中包含一组质数作为基础元素，并以乘积形式存在（比如猫耳数值为2、弱气数值为3、黄毛数值为5、病娇数值为7、双马尾数值为11以此类推）。
举个例子，正妹是双份的猫耳，而且有一份弱气，她的属性值为223=12。
当前团队成员对某一问题尤为关注，并希望找到与自己最接近且具有相同萌属性的上司。举个例子来说，在实际操作中我们通常将属性值如2、4、6及45等视为具备相同的属性特征。
然而，组员可能会随时变化自己的属性。啊。。感觉好麻烦啊。。
输入格式：
第一行，n,k 表示成员数与询问的次数
第二行，n个数，分别是1~n号成员的属性值
接下来n-1行，x_i,y_i 表示x_i是y_i的上司。
接下来来k行，有两种情况
1 u_i 询问离u_i成员最近且有相同萌元素上司。
2 u_i a 更改u_i的属性值为a
输出格式：
对于每一个类型为1的查询，请返回满足条件的所有结果编号；若无满足条件的结果，请返回-1号结果
输入样例：
4 6
10 8 4 3
1 2
2 3
3 4
1 1
1 2
1 3
1 4
2 1 9
1 4输出样例：
-1
1
2
-1
1说明提示：
对于20%的数据，没有修改的操作。
对于50%的数据，n<=100,修改次数<10
对于100%的数据，n<=200000,k<100000 ,修改次数<=50,a_i<=2^31-1
UPD：本题测试数据随机，可能是假题。
思路：
使用vector建一棵树，记录上司是谁。再用暴力dfs搜索。
实现：
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <map>
using namespace std;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n,k,a[N],x,y,op;
vector<int>v[N];
int gcd(int a,int b){
if(a<b){
swap(a,b);
}
if(a%b==0)return b;
if(a==1||b==1)return 1;
return gcd(b,a%b);
}
int dfs(int u,int pos){
int len=v[u].size();
if(len<1){
return -1;
}else{
for(int i=0;i<len;i++){
if(gcd(a[v[u][i]],a[pos])>1){
return v[u][i];
}
}
for(int i=0;i<len;i++){
return dfs(v[u][i],pos);
}
}
}
int main(){
cin >>n>>k;
for(int i=1;i<=n;i++){
cin >>a[i];
}
for(int i=1;i<=n-1;i++){
cin >>x>>y;
v[y].push_back(x);
}
for(int i=1;i<=k;i++){
cin >>op;
if(op==1){
cin >>x;
cout <<dfs(x,x)<<endl;
}else{
cin >>x>>y;
a[x]=y;
}
}
return 0;
}