2016-2017 ACM-ICPC, NEERC, Central Subregional Contest G

题意：给一个数n，求是否可以拆分成3个素数相乘

思路：素数分解是唯一的，所以只需要找到n的2个素因子啊a，b，然后判断n/(a*b)是否为素数

AC代码：

#include "iostream"
#include "string.h"
#include "stack"
#include "queue"
#include "string"
#include "vector"
#include "set"
#include "map"
#include "algorithm"
#include "stdio.h"
#include "math.h"
#define ll long long
#define bug(x) cout<<x<<" "<<"UUUUU"<<endl;
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
const int N=1e5+100;
/////2016-2017 ACM-ICPC, NEERC, Central Subregional Contest
int prime(int n){
    int flag=1;
    for(int i=2; i*i<=n; ++i){
        if((n%i)==0){
            flag=0;
            break;
        }
    }
    return flag;
}

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    cin>>n;
    int k=0,an=1;
    if(prime(n)){
        cout<<"NO";
        return 0;
    }
    for(int i=2; i*i<=n; ++i){
        if((n%i)==0){
            if(prime(i)){
                if(k<2) an*=i;
                k++;
            }
            if(prime(n/i)){
                if(k<2) an*=(n/i);
                k++;
            }
        }
    }
    if(k==3 && prime(n/an)){
        cout<<"YES";
        return 0;
    }
    cout<<"NO";
    return 0;
}

2016-2017 ACM-ICPC, NEERC, Central Subregional Contest G

相关推荐