算术基本定理--正整数唯一分解定理
(2019-01-19 11:59:26)分类: 知识点 |
一)ss1036因数个数
任给一个正整数n,求出这个正整数不同因数的个数。
如:n=6时,因为1,2,3,6这四个数均是6的因数,故输出为4。
输入 输入一个正整数
输出 输出因数个数
样例输入
6
样例输出
4
二)把一个合数分解成若干个质因数乘积的形式(即求质因数的过程)叫做分解质因数。分解质因数(也称分解素因数)只针对合数。
输入一个正整数n,将n分解成质因数乘积的形式。
输入样例:36
输出样例:36=2*2*3*3
【分析】
将 任意的n分解为质因数的乘积,要从最小的质数开始,那么,我们就不妨从2开始试除,能整除就输出2,再对商继续试除,直到不再含有因子2;然后用下一个质 数反复试除,……,再用下一个质数试除,……,一直到商为1,停止操作。这里,质因数的递增,是一层循环,每一个质因数的反复试除,又是一层循环。因此, 本题使用两层循环来解决。
三)ss2663算术基本定理=openjudge因子分解
算术基本定理可表述为:任何一个大于1的自然数 N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3......Pnan,这里P1
如6=2^1*3^1,9=3^2,50=2^1*5^2……
输入 输入一个合数自然数
输出 输出标准分解式
样例输入 1000
样例输出 1000=2^3*5^3
四)正整数唯一分解定理
算术基本定理,又称为正整数的唯一分解定理,即:每个大于1的自然数均可写为几个质数的积,而且这些质因子按大小排列之后,写法仅有一种方式。
先给出一个大于1的自然数,请将其写成质因数乘积的形式,如:
6=2*3
12=2*2*3
25=5*5
37=37
……
输入
输入一个大于1的自然数
输出
输出质因数分解等式
样例输入
12345
样例输出
12345=3*5*823
五)openjudge分解因数
给出一个正整数a,要求分解成若干个正整数的乘积,即a = a1 * a2 * a3 * ... * an,并且1 < a1 <= a2 <= a3 <= ... <= an,问这样的分解的种数有多少。注意到a = a也是一种分解。
输入
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a (1 < a <
32768)
输出
n行,每行输出对应一个输入。输出应是一个正整数,指明满足要求的分解的种数
样例输入
2
2
20
样例输出
1
4
六)coj1043因子分解:
分解一个整数n的因子,格式如下:
n = a1*a2*a3*a4.......*am
比如:
12=12
12=6*2
12=4*3
12=3*4
12=3*2*2
12=2*6
12=2*3*2
12=2*2*3
总共8种
【输入格式】
一行一个整数n(1 < n < 2^31 )。
【输出格式】
输出分解的总数。
【样例输入】
12
【样例输出】
8
参考程序:
using namespace std;
int a[11000],len;
void fz(int x)
{
int
t=int(sqrt(double(x+1)));
for(int
i=2;i<=t;i++)
{
if(x % i==0)
{
a[++len]=i;
if(x/i != i) a[++len]=x/i;
}
}
}
int n,ans;
void dfs(int d)
{
ans++;
for(int
i=1;i<=len;i++)
{
if(d*a[i] > n) break;
if(n % (d*a[i])==0 && n != d*a[i])
{
dfs(d*a[i]);
}
}
}
int main()
{
scanf("%
d",&n);
len=0;fz(n);
sort(a+1,a+len+1);
ans=0; dfs(1);
printf("%
d\n",ans);
return
0;
}
判断題:1)对 2)错
单选題:(1)A (2)C (3)B (4)C
任给一个正整数n,求出这个正整数不同因数的个数。
如:n=6时,因为1,2,3,6这四个数均是6的因数,故输出为4。
输入 输入一个正整数
输出 输出因数个数
样例输入
6
样例输出
4
二)把一个合数分解成若干个质因数乘积的形式(即求质因数的过程)叫做分解质因数。分解质因数(也称分解素因数)只针对合数。
输入样例:36
输出样例:36=2*2*3*3
【分析】
将 任意的n分解为质因数的乘积,要从最小的质数开始,那么,我们就不妨从2开始试除,能整除就输出2,再对商继续试除,直到不再含有因子2;然后用下一个质 数反复试除,……,再用下一个质数试除,……,一直到商为1,停止操作。这里,质因数的递增,是一层循环,每一个质因数的反复试除,又是一层循环。因此, 本题使用两层循环来解决。
三)ss2663算术基本定理=openjudge因子分解
算术基本定理可表述为:任何一个大于1的自然数 N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3......Pnan,这里P1
如6=2^1*3^1,9=3^2,50=2^1*5^2……
输入 输入一个合数自然数
输出 输出标准分解式
样例输入 1000
样例输出 1000=2^3*5^3
四)正整数唯一分解定理
算术基本定理,又称为正整数的唯一分解定理,即:每个大于1的自然数均可写为几个质数的积,而且这些质因子按大小排列之后,写法仅有一种方式。
先给出一个大于1的自然数,请将其写成质因数乘积的形式,如:
6=2*3
12=2*2*3
25=5*5
37=37
……
输入
输出
样例输入
12345
样例输出
12345=3*5*823
五)openjudge分解因数
给出一个正整数a,要求分解成若干个正整数的乘积,即a = a1 * a2 * a3 * ... * an,并且1 < a1 <= a2 <= a3 <= ... <= an,问这样的分解的种数有多少。注意到a = a也是一种分解。
输入
输出
样例输入
样例输出
六)coj1043因子分解:
分解一个整数n的因子,格式如下:
n = a1*a2*a3*a4.......*am
比如:
12=12
12=6*2
12=4*3
12=3*4
12=3*2*2
12=2*6
12=2*3*2
12=2*2*3
总共8种
【输入格式】
一行一个整数n(1 < n <
【输出格式】
输出分解的总数。
【样例输入】
12
【样例输出】
8
参考程序:
using namespace std;
int a[11000],len;
void fz(int x)
{
int n,ans;
void dfs(int d)
{
int main()
{
判断題:1)对 2)错
单选題:(1)A (2)C (3)B
后一篇:嵌套循环基础题二