加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

算术基本定理--正整数唯一分解定理

(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

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有