质数 唯一分解

1.第n小质数

描述

输入一个正整数n，求第n小的质数。

输入

一个不超过10000的正整数n。

输出

第n小的质数。

样例：

样例输入
10
样例输出
29

方法：合数一定可以表示成一个比它小的质数的几倍，所以若一个数不能整除比它小的所有的质数，则这个数是质数。

代码实现：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int n,z[100001],s;
bool pd;

int search(double tmp) {
    int k=(int)tmp;//将tmp强制转换成int类型，并赋值给k
    for(int i=1; i<=s; i++) {
        if(z[i]>=k)//如果有一个质数必要查找的数大
            return i+1;//因为tmp是强制转换的，比原数要小，所以i+1，宁大勿小
    }
}

int main() {
    cin>>n;
    z[1]=2,z[2]=3;//第一个质数为2，第二个质数为3
    s=2;//目前有2个质数
    while(s<n) {
        int tmp=z[s];//把目前最大的质数赋值给tmp
        s++;//质数的个数先加一
        while(1) {
            tmp++;//下一个质数至少比目前的大一
            pd=false;//将pd初始化为false
            int hind=search(sqrt(tmp));//找到要判断的数位于哪两个质数之间 
            /*例：15=3*5，枚举到3时判断了一次，5时又判断了一次，
            造成重复判断。所以判断能否整除比它小的所有的质数，
            仅需判断到根号n即可*/
            for(int i=1; i<=hind; i++) {
                if(tmp%z[i]==0) { //如果要查找数能够被一个质数整除，那它就不是质数
                    pd=true;
                    break;
                }
            }
            if(pd) continue;//如果不是质数，跳出寻找下一个数
            z[s]=tmp;//如果找到一个质数，把它存到数组中
            break;
        }
    }
    cout<<z[n]<<endl;
    return 0;
}

2.质因数分解

描述

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

输入

输入只有一行，包含一个正整数 n。

对于60%的数据，6 ≤ n ≤ 1000。
对于100%的数据，6 ≤ n ≤ 2*10^9。

输出

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

样例：

  样例输入  21 

 样例输出   7

根据唯一分解定理，若此题有答案，则输入数据满足有且只有一组质数相乘=n。

代码实现：

#include<iostream>
#include<cstdio>
#include<cmath> 
using namespace std;

int main()
{
    int n;
    cin>>n;
    int t=sqrt(n);
    for(int i=2;i<=t;i++)
    {
        if(n%i==0)//根据唯一分解，题目保证有解，所以依次枚举，如果有一个数能整除n，则为较小的质数 
        {
            cout<<n/i<<endl;//n/i则为较大的质数 
            return 0;
        }
    }
}