数论的各种板子1.0

仅为了记录所学的知识.

bool is_prime(int x){//求是否为素数 
	if(x<2) return false;
	for(int i=2;i<=x/i;++i){
		if(x%i==0) return false;
	}
	return true;
}

void divide(int x){//分解质因子 
	for(int i=2;i<=x/i;++i){
		int s=0;
		while(x%i==0) x/=i,s++;
		cout<<i<<' '<<s<<endl;
	}
	if(x>1) cout<<x<<' '<<1<<endl;
	cout<<endl;
}

void shai1(int x){//朴素筛
	for(int i=2;i<=n;++i){
		if(x%i==0){
			shu[cnt++]=i;
			for(int j=2;j<=n;j++){
				if(i*j>n) break;
				shai[i*j]=1;
			}
		}
	}
}

void shai2(int x){//欧拉筛 
	for(int i=2;i<n;i++){
		if(x%i==0) shu[cnt++]=i;
		for(int j=1;j<n;j++){
			if(shu[j]*i>n) break;
			shai[shu[j]*i]=1;
			if(shu[j]*i==0) break;
		}
	}
}

vector<int> get_divisors(int x){//分解因数，求所有约数 
	vector<int>res;//存答案 
	for(int i=1;i<=x/i;++i){
		if(x%i==0){//如果可以整除 
			res.push_back(i);//推入 
			if(i!=x/i) res.push_back(x/i);//如果不是平方的结果，推入 
		} 
	}
	//sort(res.begin(),res.end()); 不要求顺序的话，不用排序 
	return res;
}