质因数分解，找到一个质数，把这个质数除干净

bool cmp(int a){
	int ans = 0;
	for(int i=2;i*i<=a;i++){
		if(a%i==0){
			ans++;
			while(a%i==0){
				a/=i;
			}
		}
	}
	if(a!=1)ans++;
	return ans==2;
}

直接暴力枚举。看到这里先去试下怎么枚举。还是不会继续看

bool cmp(int k){  // 判断k 是不是质数
	for(int i=2;i*i<=k;i++){
		if(k%i==0)return 0;
	}
	return 1;
}
int check(int k){  // k 为怪物血量
	int i=1;   //  i 表示接下来一次攻击会对怪物造成i点伤害
	int ans=0;
	while(k>0){
		ans++;
		if(cmp(k)){  // 如果k为质数，直接KO
			return ans;
		}else{
			k = k - i;
		}
		i=i*2;
	}
	if(k==0)return ans;
	return -1;
}

#include<bits/stdc++.h>
using namespace std;
struct node{
	long long num;
	int cnt;
};
vector<node> vec;
int main() {
	long long n;
	scanf("%lld",&n);
	for(long long i=2;i*i<=n;i++){
		if(n%i==0){
			int num=i,cnt=0;
			while(n%i==0){
				cnt++;
				n/=i;
			}
			vec.push_back({num,cnt});
		}
	}
	if(n!=1){
		vec.push_back({n,1});
	}
	int ans=0;
	for(int i=0;i<vec.size();i++){
		for(int j=1;j<=vec[i].cnt;j++){
			ans++;
			vec[i].cnt -=j;
		}
	}
	cout << ans << endl;	
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
vector<long long> vec[1005];
int n,m;
long long check(int k) {
	vector<long long> temp;
	long long sum = 0;
	int t1 = vec[1].size();
	for(int i=2; i<=n; i++) {
		int id = vec[i].size()-k+1;
		if(id<0)id=0;
		for(int j=0; j<id; j++) {
			sum+=vec[i][j];
			t1++;
		}
		for(int j=id; j<vec[i].size(); j++) {
			temp.push_back(vec[i][j]);
		}
	}
	if(t1<k) {
		sort(temp.begin(),temp.end());
		int id=temp.size();// 
		id = min(id,k-t1);
		for(int j=0; j<id; j++) {
			sum+=temp[j];
			t1++;
		}
	}
	return sum;
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=m; i++) {
		long long p,c;
		scanf("%lld%lld",&p,&c);
		vec[p].push_back(c);
	}
	for(int i=1; i<=n; i++) {
		sort(vec[i].begin(),vec[i].end());
	}
	int a=vec[1].size();
	if(a==0)a=1;
	long long ans=1e18;
	for(int i=a; i<=m; i++) { //枚举第一种武器的适配为 i
		ans = min(ans,check(i));
	}
	cout<<ans << endl;
	return 0;
}