质数的和

问题描述：
输入任意的数将其分解成两个质数相加的形式，输出总共有多少总分解方式，分解因子不区分排序

输入格式：总共一行，输入被分解的数字n
输出格式：输出可以分解的所有方案，不区分顺序，最后一行输出方案个数。

例1：
输入：
100
输出：
100=3+97
100=11+89
100=17+83
100=29+71
100=41+59
100=47+53
6

思路：

用一个数组记录分解的质数，然后问题就变成了两数之和。

代码：

#include<iostream>
#include<vector>
#include<unordered_set> 
using namespace std;
int n;
const int N = 1e5+10;
int st[N];
int Prime[N];
int cnt;

void Is_prime(int x){
    for(int i = 2; i <= x; i++){
        if(!st[i]) Prime[cnt++] = i;
        for(int j = 0; Prime[j] <= x / i; j++){
            st[Prime[j] * i] = true;
            if(i % Prime[j] == 0) break;
        }
    }
}


int main(){
    cin>>n;
    Is_prime(n);
    unordered_set<int> hash;
    vector<string> res;
    for(int i = 0;i < cnt; i++) {
        //cout<<Prime[i]<<endl;
        int x = n - Prime[i];
        if(hash.count(x)){
            //cout<<x<<" " <<Prime[i]<<endl;
            string path;
            path += to_string(n);
            //cout<<n<<endl;
            path += '=';
            path += to_string(Prime[i]);
            path += '+';
            path += to_string(x);
            res.push_back(path);
            //cout<<path<<endl;
        }
        else hash.insert(Prime[i]);
    }
    for(auto s : res) cout<<s<<endl;
    cout<<res.size();
    return 0;
}