今日题算难，总是要用最优解；

约数定义：若a能整除b，则b是a的约数；

质数定义：质数只有1和它本身两个约数，只在>1的整数中讨论；

例题 J31401判定质数

http://www.turing-code.com/d/sqjx2025/p/J31401

题目描述：输入n个ai，判断每个ai是不是质数，是输出Yes，不是输出No;

方法：从2枚举所有<n的数，优化：遍历从2到n的平方根；

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
	int a;
	cin>>a;
	for(int j=1;j<=a;j++){
		int n,t=1;
		cin>>n;
		for(int i=2;i<n/i;i++){
			if(n%i==0){
				t=0;
				break;
			}
		}
		if(n==1){
			cout<<"No"<<endl;
			continue;
		}
		if(t==0)cout<<"No"<<endl;
		else if(t==1)cout<<"Yes"<<endl;
	}
	return 0;
}

2例题 J31403找质数

http://www.turing-code.com/d/sqjx2025/p/J31403 题目描述：

方法：从2开始遍历数，若该数未标记，则为质数并要标记它<n的倍数；

代码：

#include<bits/stdc++.h>
using namespace std;
int v[10000010];
int main() {
	int n,sum=0;
	cin>>n;
	for(int i=2;i<=n;i++){
		if(v[i]==1)continue;
		sum++;
		for(int j=2;j<=n/i;j++){
			if(i*j>n)break;
			v[i*j]=1;
		}
	}
	cout<<sum;
	return 0;
}

J31404求约数

http://www.turing-code.com/d/sqjx2025/p/J31404

思路:遍历从1到n的平方根，若n可以整除i并且ii!=n，此时，i和n/i都是n的约数，若n可以整除i但是ii==n，i为n的约数，这样可以去重；

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		long long a;
		cin>>a;
		vector<int>x;
		for(int j=1;j<=a/j;j++){
			if(a%j==0&&a/j!=0){
				x.push_back(j);
				x.push_back(a/j);
			}
			else if(a%j==0)x.push_back(j);
		}
		sort(x.begin(),x.end());
		for(int j=0;j<x.size();j++)cout<<x[j]<<" ";
		cout<<endl;
	}
	return 0;
}

J31402分解质因数

http://www.turing-code.com/d/sqjx2025/p/J31402

题目思路：遍历从2到a的平方根，找出能被a整除的质数，也就是a的质因数，输出它；

正确代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	for(int j=1;j<=n;j++){
		int a;
		cin>>a;
		for(int i=2;i*i<=a;i++){
			if(a%i==0){
				int x=0;
				while(a%i==0){
					a/=i;
					x++;
				}
				cout<<i<<" "<<x<<endl;
			}
		}
		if(a>1)cout<<a<<" 1"<<endl;
		cout<<endl;
	}
	return 0;
}

J31407 最大公约数

http://www.turing-code.com/d/sqjx2025/p/J31407

题目描述：输入n，输入n个ai,bi，输出它们的最大公因数；

#include<bits/stdc++.h>
using namespace std;
int v(int a,int b){
	while(b!=0){
		int x=b;
		b=a%b;
		a=x;
	}
	return a;
}
int main(){
	int n;
	cin>>n;
	while(n--){
		int a,b;
		cin>>a>>b;
		cout<<v(a,b)<<endl;
	}
	return 0;
}

182.快速幂

http://www.turing-code.com/d/sqjx2025/p/182 快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在 \Theta(\log n) 的时间内计算 a^n 的小技巧，而暴力的计算需要 \Theta(n) 的时间。