前引

由于x最大是1e9,并且有T组数据，因此用for循环便利x寻找多少个因子，判断是否是质数，最坏的时间复杂度是O(n^3)。

因此我们需要用另一种更加简洁的方法来做本道题。

例：48 = 2^4 * 3^1 我们要做的是将一个数写成质因子的乘方相乘

如何写呢？

主要代码解析

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main()
{
	for(int i=2;i <= sqrt(n+1e-6);i ++)    
		{
   	         if(n%i==0)                 
			{
				v.push_back(i);
				f = 0;
			}
			while(n%i==0)
			{
				n=n/i;
			}
		}
  return 0;
}

此代码块用vector->"v"存储n的所有种类的质因子。

其中 sqrt(n+1e-6) 指 n的开方。因为质因子永远不会超过n的开方，可以减少时间复杂度。

接下来是重要板块。

while循环是一口气把这个质因子的x次方除以完，也就相当于除以质因子的x次方。

但是为什么前面是只要i是n的因子就可以被除呢？打个比方，n=48，刚开始你除以了2^4，那么后面的4也是48的因子，不过48已经把所有的2除以玩了，因此48编程3，除以不动2了。

剩下部分

剩下的部分就是简单易懂的输入输出套进去

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main(){
	int T;
	cin>>T;
	for(int i = 1;i <= T;i ++)
	{
		int n;
	   cin>>n;
	   vector<int>v;int f = 1;
	   for(int i=2;i <= sqrt(n+1e-6);i ++)
	   {
            if(n%i==0)
            {
                v.push_back(i);
			     f = 0;
            }
            while(n%i==0)
            {
                n=n/i;
            }
        } 
	   if(n>1)v.push_back(n);
	   if(f==1)
	   {
		  cout<<"isprime"<<endl;
		  cout<<n<<endl;
	   }
	   else
	   {
		  cout<<"noprime"<<endl;
		  for(int i = 0;i < v.size();i ++)
		  {
		      	cout<<v[i]<<" ";
	       	}
	   	   cout<<endl;
    	}
	}
return 0;
}

就问详细不详细吧 awa