求质因数问题

求质因数问题

一、求一个数的所有质因数（尤其n很大时）

我刚开始想的是观察题目给的数据范围，预处理出能够满足这个范围的所有素数，也就是2~sqrt(n)范围内的素数，然后根据输入的n一次遍历这些素数，判断是否整除，但是有一个bug是这种方法只能求出sqrt(n)以内的质因数。所以这个方法不可行。

可行方案：

long long a[],n,cnt=0;
for(int i=2;i*i<=n;i++){if(n%i==0){a[cnt++]=i;while(n%i==0)n/=i;}
}
if(n>1) a[cnt++]=n; 

在素数筛的时候加了一个vector数组就实现了。

这里其实就用到了我上面的想法，不过正如你所看到的这种方法只能求n不大的。

int vis[100010];//测试了一下，10^6的时候就很慢了，所以用来做最多10^5的数 
vector<int>a[100010];
memset(vis,0,sizeof(vis));
for(int i=0;i<100010;i++)a[i].clear();
for(int i=2;i<100010;i++){if(!vis[i]){vis[i]=1;a[i].push_back(i); for(int j=2;j*i<100010;j++){vis[j*i]=1;a[j*i].push_back(i);}}
}