NOIP 2012 质因数分解(数学)

比眉伴天荒 2022-05-17 12:46 375阅读 0赞

题目描述

已知正整数n是两个不同的质数的乘积，试求出较大的那个质数。

输入

每组输入数据只有一行，包含一个正整数n。  
  
  
数据规模：  
对于60%的数据，6≤n≤1000。  
对于100%的数据，6≤n≤2\*109。

输出

每组输出只有一行，包含一个正整数p，即较大的那个质数。

分析：任何一个大于1的自然数 ![b3fb43166d224f4a43e792300bf790529822d193.jpg][] ，都可以唯一分解成有限个质数的乘积 ![f703738da97739129c546742fa198618367ae2a7.jpg][] ，这里 ![8c1001e93901213f06c3c6c456e736d12f2e9532.jpg][] 均为质数。而题上已告诉这个数是两个质数的乘积，也就是说在>1，<它自己的数中，只有两个数能够整除这个数，因此从小到大枚举每个数，能整除的时候，就输出另一个数，就是较大的那个质数。。。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const int inf=0x3f3f3f3f;
    
    int read()
    {
        char ch=getchar();int ret=0,f=1;
        while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
        return f*ret;
    }
    
    void slove(int n)
    {
        rfup(i,2,n)
        {
            if(n%i==0){
                printf("%d\n",n/i);
                return;
            }
        }
    }
    
    int main()
    {
        int n=read();
        slove(n);
        return 0;
    }

[b3fb43166d224f4a43e792300bf790529822d193.jpg]: https://gss3.bdstatic.com/-Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D14/sign=7896797ddfc451daf2f608efb6fd720b/b3fb43166d224f4a43e792300bf790529822d193.jpg
[f703738da97739129c546742fa198618367ae2a7.jpg]: https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D124/sign=ae84eec8b4fd5266a32b38169f189799/f703738da97739129c546742fa198618367ae2a7.jpg
[8c1001e93901213f06c3c6c456e736d12f2e9532.jpg]: https://gss2.bdstatic.com/-fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D115/sign=69e7dd71272dd42a5b0905aa363a5b2f/8c1001e93901213f06c3c6c456e736d12f2e9532.jpg