本蒟蒻第一篇题解
使用算法：
DFS
核心：
我们知道，所有素数除了
所以：
-
这个素数不为
2 ，那么：这个素数加减想成为另一个素数 ，只能加减2 。 -
这个素数等于
2 ，那么：这个素数加减想成为另一个素数 ，只能加上另一个不为2 的素数。
原理都知道啦题目还不简单嘛。
所以，看看下面比较长的代码吧。
#include <iostream>
#include <cmath>
/*
听我一句忠告：
不要用bits，不要用bits，不要用bits！
*/
using namespace std;//名字空间
long long a,b;
bool flag=false;
long long f[100];//用f存答案
bool prime(long long x)//普通筛，懒得写线性筛
{
if(x==0||x==1)return false;//1||0不是素数
if(x%2==0&&x!=2)return false;//非2偶数更不是
if(x==2)return true;//2是素数
for(int i=3; i<=sqrt(x); i+=2)
/*
为什么要开根？
很简单：
16是不是素数？
16=2^4
开根相当于将它的质因数完全一样的分成两份，连它的质因数的一半
都不是素数那它会是素数吗？
至于i+=2嘛，偶数直接跳过
*/
if(x%i==0)return false;//根据素数的定义来判断它是否是素数
return true;// 剩下的都是啦
}
void dfs(long long x,long long y,int step)
//用x代表A素数，用y代表B素数，用step代表素数个数
{
if(flag)return;//找到了直接走
if(prime(abs(x-y)))//abs是必要的，如果去掉，会判断一个负数是不是素数
{
cout<<step+1<<endl<<a<<" ";//上次是step+2,这次是step+1
for(int i=1; i<=step-1; i++)//去掉尾
cout<<f[i]<<" ";
cout<<b;
flag=true;//打上标记
return;
}
if(x!=2)//分为两种情况：1.两个奇数；2.一奇一偶
for(int i=1; i<=3; i++)
{
/*
关于prime（x +/- 2）：
我们知道，所有素数除了2外都是奇数，而且奇+奇=偶
所以：
1.这个prime不为2，那么：这个prime加减想成为另一个prime，只能加减2
2.这个prime=2，那么：这个prime加减想成为另一个prime，只能加上另一个不为 2的素数
*/
if(i==1&&prime(x-2))f[step]=2,dfs(2,y,step+1);
if(i==2&&prime(x-2))f[step]=x-2,dfs(x-2,y,step+1);
if(i==3&&prime(x+2))f[step]=x+2,dfs(x+2,y,step+1);
}
else if(prime(y+2))//一奇一偶的情况
f[step]=y+2,dfs(y+2,y,step+1);//一样的道理
}
signed main()
{
cin>>a>>b;
if(prime(abs(a-b)))//特判，如果AB直接可达，那么直接输出
{
cout<<2<<endl<<a<<" "<<b;
return 0;
}
dfs(a,b,1);//出发
if(!flag)//判断不可能
cout<<"-1";
return 0;//完结撒花
}