CCFCSP202312-2因子化简 （质数筛法）C/C++ 满分

C/C++题解：

具体思路：先用质数筛法找到1000以内的全部质数，然后逐一处理即可

#include<bits/stdc++.h>using namespace std;int q;long long n,k,ans;vector<long long> Sushu;void is_prime(){ bool isPrime[1001];for(int i=2;i<=1000;i++){isPrime[i]=true;} for(int i=2;i*i<=1000;i++){if(isPrime[i]){for(int j=i*i;j<=1000;j+=i){isPrime[j]=false;}}}for(int i =2;i<=1000;i++){if(isPrime[i]){Sushu.push_back(i);}}}//false为合数 int main(){is_prime();cin >> q;while(q--){cin >> n >> k;ans = 1;int flag = 0,curK = 0;while(n>1&&flag<Sushu.size()){if(n%Sushu[flag] == 0){curK ++;n /= Sushu[flag];}else{if(curK<k){curK = 0;flag++;continue;}for(int i = 0;i<curK;i++){ans*=Sushu[flag];}curK = 0;flag++;}}if(curK >= k){for(int i = 0;i<curK;i++){ans*=Sushu[flag];}}cout << ans << endl;}} 

···