首页 > 代码库 > 3164 质因数分解
3164 质因数分解
3164 质因数分解
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 黄金 Gold
题目描述 Description
（多数据）给出t个数，求出它的质因子个数。
数据没坑，难度降低。
输入描述 Input Description
第一行 t
之后t行 数据
输出描述 Output Description
t行 分解后结果（质因子个数）
样例输入 Sample Input
2
11
6
样例输出 Sample Output
1
2
数据范围及提示 Data Size & Hint
(样例解释)11自己本身是一个质数，所以计入其中。
顺便提示：t<=100000。每个数小于long long unsigned 呵呵
分类标签 Tags 点此展开
枚举 编程能力题
第一次，直接上唯一分解定理，结果WA+TLE ？？
WA代码：
#include<cstdio>#include<iostream>#include<cmath>#include<vector>using namespace std;#define ll unsigned long long#define pir pair<ll,ll>vector<pir> f;inline const ll read(){ register ll x=0; register char ch=getchar(); while(ch<‘0‘||ch>‘9‘) ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar(); return x;}void deal(ll x){ f.clear(); ll m=floor(sqrt(x)+0.5); for(ll i=2;i<=m;i++){ if(x%i) continue; ll q=0; while(x%i==0) q++,x/=i; f.push_back(make_pair(i,q)); } if(x>1) f.push_back(make_pair(x,1)); printf("%d\n",f.size());}int main(){ ll T,n; T=read(); while(T--) n=read(),deal(n); return 0;}
暴力过掉
AC代码：
#include<iostream>using namespace std;int main(){ ios::sync_with_stdio(false); int T;long long n; cin>>T; while(T--){ cin>>n; int tot=0; for(int i=2;i<=n;i++){ if(n==1) break; if(n%i==0){ do{ n/=i; tot++; }while(n%i==0); } } cout<<tot<<endl; } return 0;}
3164 质因数分解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。